Résolution avec Ruby et Python AtCoder ABC057 C Décomposition du facteur premier Recherche complète de bits

introduction

• AtCoder Problems * Utilise les recommandations pour résoudre les problèmes passés. Merci à AtCoder et AtCoder Problems.

~~ De plus, la langue a été mise à jour dans les questions précédentes depuis hier. ~~ ** Addenda ** Il semble qu'il était une fois retourné à l'ancien environnement.

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

Je ne savais pas comment vérifier la version de Numo :: NArray.

Ce thème

AtCoder Beginner Contest C - Digits in Multiplication Difficulty: 834

Ce thème, décomposition des facteurs premiers + recherche complète de bits Ruby Je l'ai déjà résolu, * Factorisation principale AtCoder CADDi 2018 C à résoudre avec Ruby, Perl, Java et Python * Cela semble être un problème similaire, alors copiez-le immédiatement ~~ ~~ Résolvons-le.

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

Si vous utilisez la méthode d'allocation des nombres premiers par ordre décroissant, vous obtiendrez WA, nous utilisons donc une recherche complète de bits.

bit.rb

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

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

Dans la recherche de bits complète, «répétée_permutation» est également utilisée, mais ici, cela semble être «TLE». 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

Si c'est «/ =», cela semble être «WA».

Résumé

• ABC 057 résolu C
• La langue des questions précédentes d'AtCoder a été mise à jour
• Familiarisez-vous avec Ruby
• Familiarisez-vous avec Python