Lösen mit Ruby und Python AtCoder ABC057 C Zerlegung des Primfaktors Bit vollständige Suche

Einführung

• AtCoder-Probleme * Verwendet Empfehlungen, um frühere Probleme zu lösen. Dank AtCoder und AtCoder Probleme.

~~ Außerdem wurde die Sprache in den letzten Fragen seit gestern aktualisiert. ~~ ** Nachtrag ** Es scheint, dass es einmal in die alte Umgebung zurückgekehrt war.

ruby
"2.7.1"

python
Python: 3.8.2
NumPy:  1.18.2
SciPy:  1.4.1

pypy3
Python: 3.6.9

cython
Python: 3.8.2

Ich wusste nicht, wie ich die Version von Numo :: NArray überprüfen sollte.

Dieses Thema

AtCoder Beginner Contest C - Digits in Multiplication Difficulty: 834

Dieses Thema, Primfaktor-Zerlegung + Bit-Vollsuche Ruby Ich habe es zuvor gelöst. * AtCoder CADDi 2018 C-Primfaktorisierung zur Lösung mit Ruby, Perl, Java und Python ~~ Lass es uns lösen.

ruby.rb

require 'prime'

n = gets.to_i
if n == 1
  puts 1
else
  h = Prime.prime_division(n).to_h
  p = []
  h.each do |k, v|
    while v > 0
      p << k
      v -= 1
    end
  end
  min = Float::INFINITY
  0.upto(2 ** p.size - 1) do |bit|
    a = 1
    b = 1
    p.size.times do |i|
      if bit[i] == 0
        a *= p[i]
      else
        b *= p[i]
      end
    end
    if a >= b
      min = a if min > a
    else
      min = b if min > b
    end
  end
  puts min.to_s.size
end

Wenn Sie die Methode zum Zuweisen von Primzahlen in absteigender Reihenfolge verwenden, erhalten Sie "WA", daher verwenden wir die Bit-Vollsuche.

bit.rb

  0.upto(2 ** p.size - 1) do |bit|

  [0, 1].repeated_permutation.each do |bit|

Bei der Bit-Vollsuche wird auch "wiederholte_Permutation" verwendet, aber hier scheint es "TLE" zu sein. Python

pypy.py

from math import sqrt
from itertools import product
import sys

n = int(input())
p = []
def factorization(arg):
    while arg % 2 == 0:
        p.append(2)
        arg //= 2
    for i in range(3, int(sqrt(arg)) + 1, 2):
        while arg % i == 0:
            p.append(i)
            arg //= i
    if arg > 1:
        p.append(arg)
if n == 1:
    print(1)
else:
    factorization(n)
    min = sys.maxsize
    for bit in range(2 ** len(p)):
        a = 1
        b = 1
        for i in range(len(p)):
            if ((bit >> i) & 1):
                a *= p[i]
            else:
                b *= p[i]
        if min > a and a >= b:
            min = a
        elif min > b and b > a:
            min = b
    print(len(str(min)))

int.py

            arg //= i

Wenn es "/ =" ist, scheint es "WA" zu sein.

Zusammenfassung

• ABC 057 Gelöst C.
• Die frühere Fragensprache von AtCoder wurde aktualisiert
• Machen Sie sich mit Ruby vertraut
• Machen Sie sich mit Python vertraut