結果
問題 |
No.1312 Snake Eyes
|
ユーザー |
|
提出日時 | 2021-06-16 09:36:56 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 110 ms / 2,000 ms |
コード長 | 572 bytes |
コンパイル時間 | 196 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 59,136 KB |
最終ジャッジ日時 | 2024-12-29 22:13:49 |
合計ジャッジ時間 | 8,061 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 85 |
ソースコード
n=int(input()) ans=n-1 # p<=10**6の探索 for i in range(2,10**6+1): nn=n t=nn%i nn//=i flg=True while nn: if t==nn%i: nn//=i else: flg=False break if flg: print(i) exit() if n<10**6: print(ans) exit() # p>=10**6の探索 # ぞろ目になっても2桁を超えない st=set() for i in range(1,int(n**.5)+1): if n%i==0: if n//i-1>=10**6: st.add(i) if i>=10**6: st.add(n//i) # n=x*(p+1)=x*p+x # x:nの約数 for x in st: p=n//x p-=1 if p>=10**6 and n%p==(n//p)%p: ans=min(ans,p) print(ans)