結果
問題 |
No.1611 Minimum Multiple with Double Divisors
|
ユーザー |
|
提出日時 | 2021-08-03 04:37:01 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,846 bytes |
コンパイル時間 | 254 ms |
コンパイル使用メモリ | 82,308 KB |
実行使用メモリ | 97,892 KB |
最終ジャッジ日時 | 2024-09-16 14:51:53 |
合計ジャッジ時間 | 7,316 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | -- * 2 |
other | TLE * 1 -- * 36 |
ソースコード
def is_prime_MR(n): if n in [2,7,61]: return True if n<2 or n%2==0: return False d=n-1 d=d//(d&-d) L=[2,7,61] if n<1<<32 else [2,3,5,7,11,13,17] if n<1<<48 else [2,3,5,7,11,13,17,19,23] if n<1<<61 else [2,3,5,7,11, 13,17,19,23, 29,31,37] for a in L: t=d y=pow(a,t,n) if y==1: continue while y!=n-1: y=(y*y)%n if y==1 or t==n-1: return False t<<=1 return True def prime_counter(n): i=2 ret={} mrFlg=0 while i*i<=n: k=0 while n%i==0: n//=i k+=1 if k: ret[i]=k i+=1+i%2 if i==101 and n>=2**20: while n>1: if is_prime_MR(n): ret[n],n=1,1 else: mrFlg=1 j=_find_factor_rho(n) k=0 while n%j==0: n//=j k+=1 ret[j]=k if n>1: ret[n]=1 if mrFlg>0: ret={x:ret[x] for x in sorted(ret)} return ret def divisors(n): """ O(x^1/4) O(10**9)の整数10**4個の約数列挙が可能 """ primes=prime_counter(n) P=set([1]) for key,value in primes.items(): Q=[] for p in P: for k in range(value+1): Q.append(p*pow(key,k)) P|=set(Q) return P def _find_factor_rho(n): m=1<<n.bit_length()//8+1 for c in range(1,99): f=lambda x:(x*x+c)%n y,r,q,g=2,1,1,1 while g==1: x=y for i in range(r): y=f(y) k=0 while k<r and g==1: ys=y for i in range(min(m,r-k)): y=f(y) q=q*abs(x-y)%n g=gcd(q,n) k+=m r<<=1 if g==n: g=1 while g==1: ys=f(ys) g=gcd(abs(x-ys),n) if g<n: if is_prime_MR(g): return g elif is_prime_MR(n//g): return n//g ################################################################################################ import sys input=sys.stdin.readline from math import gcd T=int(input()) for _ in range(T): x=int(input()) res=float("inf") cnt=1 for key,val in prime_counter(x).items(): cnt*=(val+1) for k in range(2,32): cnt2=1 for key,val in prime_counter(x*k).items(): cnt2*=(val+1) if cnt2==cnt*2: res=min(res,x*k) print(res)