結果
| 問題 | No.1611 Minimum Multiple with Double Divisors |
| ユーザー |
 shotoyoo
|
| 提出日時 | 2021-07-21 21:49:17 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 3,400 bytes |
| コンパイル時間 | 289 ms |
| コンパイル使用メモリ | 82,560 KB |
| 実行使用メモリ | 126,912 KB |
| 最終ジャッジ日時 | 2024-07-17 17:40:36 |
| 合計ジャッジ時間 | 7,340 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | TLE | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
ソースコード
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(2*10**5+10)
write = lambda x: sys.stdout.write(x+"\n")
debug = lambda x: sys.stderr.write(x+"\n")
writef = lambda x: print("{:.12f}".format(x))
def hurui(n):
"""線形篩
pl: 素数のリスト
mpf: iを割り切る最小の素因数
"""
pl = []
mpf = [None]*(n+1)
for d in range(2,n+1):
if mpf[d] is None:
mpf[d] = d
pl.append(d)
for p in pl:
if p*d>n or p>mpf[d]:
break
mpf[p*d] = p
return pl, mpf
from collections import defaultdict
def factor(num):
d = defaultdict(int)
if num==1:
d.update({1:1})
return d
while num>1:
d[mpf[num]] += 1
num //= mpf[num]
return d
def fs(num):
f = factor(num)
ans = [1]
for k,v in f.items():
tmp = []
for i in range(len(ans)):
val = 1
for _ in range(v):
val *= k
ans.append(ans[i]*val)
return ans
pl, mpf = hurui(10**6)
from math import gcd
import random
def is_prime(n):
"""miller_rabinによる素数判定
※ 1は素数と扱う
"""
l = [2,3,5,7,11,13,17,19,23,29,31,37]
if n==1 or n in l:
return True
d = n-1
s = 0
while d%2==0:
s += 1
d //= 2
for a in l:
v = pow(a,d,n)
if v==1 or v==n-1:
continue
for _ in range(s):
v = v*v % n
if v==n-1:
break
else:
return False
return True
def rho(n):
"""nを割り切る3以上の素数を返す(素数のときnを返す)
"""
if is_prime(n):
return n
while True:
x = y = random.randint(1,n-1)
g = 1
while g==1:
x = (x*x - 3) % n
y = (y*y - 3) % n
y = (y*y - 3) % n
g = gcd((x-y), n)
if g>1:
return rho(g)
def factor(n):
"""高速な素因数分解
"""
if n==1:
return {}
f = is_prime(n)
if f:
return {n:1}
ans = {}
while n%2==0:
ans.setdefault(2, 0)
ans[2] += 1
n //= 2
v = rho(n)
while v!=n and n>1:
ans.setdefault(v, 0)
while n%v==0:
n //= v
ans[v] += 1
if n>3 and is_prime(n):
ans.setdefault(n,0)
ans[n] += 1
return ans
v = rho(n)
if n>1:
ans.setdefault(n, 0)
ans[n] += 1
return ans
t = int(input())
ans = []
for i in range(t):
x = int(input())
f = factor(x)
for p in pl:
if p not in f:
res = p
break
else:
assert 0
kvs = sorted(f.items())
count = [-1]*(40) # 回数がiの素数の最小
for k,v in kvs[::-1]:
count[v] = k
for i in range(1,40):
if count[i]==-1:
continue
res = min(res, pow(count[i], i+1))
r = 1
for l in range(1, 40):
if r<l:
r = l
if count[l]==-1:
continue
while r+1<40 and count[r+1]>=0:
r += 1
if r>=2*l:
val = 1
for i in range(l, 2*l+1):
assert count[i]>0
val *= count[i]
res = min(res, val)
ans.append(res*x)
write("\n".join(map(str, ans)))