~~ In addition, the language has been updated in the past questions since yesterday. ~~ ** Addition ** It seems that it was once returned to the old environment.
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
I didn't know how to check the version of Numo :: NArray.
AtCoder Beginner Contest C - Digits in Multiplication Difficulty: 834
This theme, prime factorization + bit full search Ruby I solved it before, * AtCoder CADDi 2018 C prime factorization to solve with Ruby, Perl, Java and Python * It seems to be a similar problem, so copy it immediately ~~ ~~ Let's solve it.
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
If you use the method of allocating prime numbers in descending order, you will get WA
, so we are using bit full search.
bit.rb
0.upto(2 ** p.size - 1) do |bit|
[0, 1].repeated_permutation.each do |bit|
The bit full search also uses repeated_permutation
, but here it seems to be 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
If it is / =
, it seems to be WA
.
Ruby(2.3.3) | Ruby(2.7.1) | Python | PyPy3(2.4.0) | PyPy3(7.3.0) | |
---|---|---|---|---|---|
Code length(Byte) | 506 | 506 | 763 | 763 | 763 |
Execution time(ms) | TLE | 1355 | TLE | 643 | 352 |
memory(KB) | 2300 | 9284 | 3064 | 52736 | 30112 |
Recommended Posts