結果
問題 | No.1339 循環小数 |
ユーザー |
👑 ![]() |
提出日時 | 2021-01-23 17:36:22 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 480 ms / 2,000 ms |
コード長 | 1,570 bytes |
コンパイル時間 | 846 ms |
コンパイル使用メモリ | 82,312 KB |
実行使用メモリ | 129,444 KB |
最終ジャッジ日時 | 2024-12-31 07:30:21 |
合計ジャッジ時間 | 8,242 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 36 |
ソースコード
"""https://yukicoder.me/problems/no/1339循環節は、10^K = 1 (mod N) となるKを求めれば行けるK == 0 が満たしてしまうので10^(K-1) == 10^(-1) (mod N) となるK-1を求めてあげればよい"""import sysimport mathfrom sys import stdin#aのmodを法にした逆元を返す#法が素数でなくても利用可能#aとmodが互いに素でないならば、-1を返すimport mathdef extGCD(a,b):g = math.gcd(a,b)x, y, u, v = 1, 0, 0, 1while b:k = a // bx -= k * uy -= k * vx, u = u, xy, v = v, ya, b = b, a % breturn g ,x, ydef exinv(a,mod):g,x,y = extGCD(a,mod)if g != 1:return -1if x > 0:return xelse:return x + mod# X^K = Y (mod M)from math import ceil, sqrtdef BsGs(X,Y,M):dic = {}dic[1] = 0sq = ceil(M**0.5)#baby-stepZ = 1for i in range(sq):Z = Z * X % Mif Z not in dic:dic[Z] = i+1if Y in dic:return dic[Y]#giant-stepR = exinv(Z,M)for i in range(1,sq+1):Y = Y * R % Mif Y in dic:return dic[Y] + i * sqreturn -1#print (BsGs(10,247,2469))TT = int(stdin.readline())for loop in range(TT):N = int(stdin.readline())while N % 2 == 0:N //= 2while N % 5 == 0:N //= 5if N == 1:print (1)else:r = 10#print (exinv(r,N),N,file=sys.stderr)k = BsGs(r,exinv(r,N),N)print (k+1)