結果
問題 | No.1915 Addition |
ユーザー |
![]() |
提出日時 | 2022-04-29 21:27:18 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 100 ms / 2,000 ms |
コード長 | 3,161 bytes |
コンパイル時間 | 939 ms |
コンパイル使用メモリ | 82,300 KB |
実行使用メモリ | 76,788 KB |
最終ジャッジ日時 | 2024-06-29 02:45:51 |
合計ジャッジ時間 | 3,138 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 10 |
ソースコード
import sysinput = sys.stdin.readlinedef gcd(a, b):while b: a, b = b, a % breturn adef isPrimeMR(n):d = n - 1d = d // (d & -d)L = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]for a in L:t = dy = pow(a, t, n)if y == 1: continuewhile y != n - 1:y = (y * y) % nif y == 1 or t == n - 1: return 0t <<= 1return 1def findFactorRho(n):m = 1 << n.bit_length() // 8for c in range(1, 99):f = lambda x: (x * x + c) % ny, r, q, g = 2, 1, 1, 1while g == 1:x = yfor i in range(r):y = f(y)k = 0while k < r and g == 1:ys = yfor i in range(min(m, r - k)):y = f(y)q = q * abs(x - y) % ng = gcd(q, n)k += mr <<= 1if g == n:g = 1while g == 1:ys = f(ys)g = gcd(abs(x - ys), n)if g < n:if isPrimeMR(g): return gelif isPrimeMR(n // g): return n // greturn findFactorRho(g)def primeFactor(n):i = 2ret = {}rhoFlg = 0while i*i <= n:k = 0while n % i == 0:n //= ik += 1if k: ret[i] = ki += 1 + i % 2if i == 101 and n >= 2 ** 20:while n > 1:if isPrimeMR(n):ret[n], n = 1, 1else:rhoFlg = 1j = findFactorRho(n)k = 0while n % j == 0:n //= jk += 1ret[j] = kif n > 1: ret[n] = 1if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}return retdef yakusu(N):c=primeFactor(N)A=list(c.keys())B=list(c.values())S=len(A)cou=1for i in B:cou*=(i+1)yakusulist=[1]*coufor i in range(cou):a=ifor j in range(S):yakusulist[i]*=pow(A[j],a%(B[j]+1))a//=(B[j]+1)yakusulist.sort()return yakusulistdef phi(n):c=primeFactor(n)A=list(c.keys())for i in A:n=n*(i-1)//ireturn nimport mathdef extgcd(A,B):a,b=max(A,B),min(A,B)if a==1 and b==0:return 1,0else:s=a//bt=a%bc,d=extgcd(b,t)if A<B:return c-s*d,delse:return d,c-s*d#251896766の時うまく行ってない?def root(P):#Pの原子根L=yakusu(P-1)for i in range(2,P):for k in L:if pow(i,k,P)==1 and k!=P-1:breakif k==P-1:return iL=list()L.append(list())for k in range(1,18):T=list()L.append(yakusu(10**k-1))T=int(input())for i in range(T):N=int(input())S=yakusu(N)flag=Falsefor k in range(1,18):for x in S:for y in L[k]:if 10**(k-1)<=(x*y-N)<10**k:print(x*y-N)flag=Truebreakif flag:breakif flag:break