結果
問題 | No.1339 循環小数 |
ユーザー |
|
提出日時 | 2021-01-15 22:32:32 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 646 ms / 2,000 ms |
コード長 | 1,486 bytes |
コンパイル時間 | 733 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 153,728 KB |
最終ジャッジ日時 | 2024-11-26 16:24:20 |
合計ジャッジ時間 | 9,642 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 36 |
ソースコード
import sysinput = lambda : sys.stdin.readline().rstrip()sys.setrecursionlimit(2*10**5+10)write = lambda x: sys.stdout.write(x+"\n")_print = lambda *x: print(*x, file=sys.stderr)def gcd2(a, b):"""a*x + b*y = gcd(a,b)なるx,yも求める"""l = []while b:l.append(divmod(a,b))a, b = b, a%bx, y = 1, 0for aa,bb in l[::-1]:x, y = y, x - aa*yreturn a, x, ydef modinv(x, M):"""素数ではないM、Mと互いに素なxに対しx * y == 1 mod M なるyを求める"""a,xx,yy = gcd2(x,M)return a,xx%M### 離散対数問題def dlog(x,y,M):"""pow(x,i,M)==y なるiを返す存在しない場合Noneを返す"""l = int(M**0.5)+1s = set()d = {}v = x%Mfor i in range(1,l+2):s.add(v)d[v] = iv *= xv %= Mv = y# print(d)_,tmp = modinv(pow(x,l,M), M)# tmp = pow(pow(x,l,M), M-2, M)for i in range(l+1):if v in s:vv = x%Mfor j in range(1,l+2):if vv==v:breakvv *= xvv %= M# j = d[v]return i*l + jv *= tmpv %= Mreturn Nonet = int(input())from math import gcdfor _ in range(t):n = int(input())while n%2==0:n //= 2while n%5==0:n //= 5if n==1:ans = 1else:ans = dlog(10,1,n)print(ans)