結果
問題 | No.1339 循環小数 |
ユーザー |
![]() |
提出日時 | 2021-01-15 22:15:19 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 127 ms / 2,000 ms |
コード長 | 937 bytes |
コンパイル時間 | 326 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 63,872 KB |
最終ジャッジ日時 | 2024-11-26 15:47:49 |
合計ジャッジ時間 | 3,759 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 36 |
ソースコード
from math import gcddef lcm(X):r=X[0]for i in range(len(X)):r=r*X[i]//gcd(r,X[i])return rdef f(x):r=[]for i in range(2,int(x**0.5)+1):if x%i==0:r.append([i,0])while x%i==0:x//=ir[-1][1]+=1if x>1:r.append([x,1])return rdef d(x):r=[]for i in range(1,int(x**0.5)+1):if x%i==0:r.append(i)if i*i!=x:r.append(x//i)r.sort()return rdef l(x):if len(x)==1:if x[0][0]==2:if x[0][1]<=2:return x[0][1]else:return 2**(x[0][1]-2)else:return (x[0][0]**(x[0][1]-1))*(x[0][0]-1)return lcm([l([x[i]]) for i in range(len(x))])def solve():N=int(input())while N%2==0:N//=2while N%5==0:N//=5if N==1:print(1)return 0X=d(l(f(N)))for j in range(len(X)):if pow(10,X[j],N)==1:print(X[j])return 0for i in range(int(input())):solve()