結果
問題 | No.1255 ハイレーツ・オブ・ボリビアン |
ユーザー |
👑 ![]() |
提出日時 | 2020-08-15 04:15:42 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 965 bytes |
コンパイル時間 | 166 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 52,352 KB |
最終ジャッジ日時 | 2024-06-28 05:39:39 |
合計ジャッジ時間 | 1,443 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 1 |
other | WA * 15 |
ソースコード
#素因数分解def Prime_Factorization(N):if N<0:R=[[-1,1]]else:R=[]N=abs(N)k=2while k*k<=N:if N%k==0:C=0while N%k==0:C+=1N//=kR.append([k,C])k+=1if N!=1:R.append([N,1])if not R:R.append([N,1])return R#Euler's Totient関数def Euler_Totient(N):N=abs(N)if N==1:return 1H=Prime_Factorization(N)R=1for (p,e) in H:R*=p**(e-1)*(p-1)return R#約数全部def Divisors(N):N=abs(N)L,U=[],[]k=1while k*k <=N:if N%k== 0:L.append(k)if k!=N//k:U.append(N//k)k+=1return L+U[::-1]#================================================N=int(input())M=2*N-1D=Euler_Totient(M)L=Divisors(D)for a in L:T=pow(2,a,M)if (T-1)%M==0:print(a)break