結果
問題 | No.308 素数は通れません |
ユーザー |
![]() |
提出日時 | 2015-12-03 17:07:24 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,896 bytes |
コンパイル時間 | 1,514 ms |
コンパイル使用メモリ | 167,580 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-09-14 08:28:16 |
合計ジャッジ時間 | 4,000 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 106 WA * 1 |
コンパイルメッセージ
main.cpp: In function ‘int bigIntMillerRabinSuspect(int, __int128)’: main.cpp:31:20: warning: ‘next’ may be used uninitialized in this function [-Wmaybe-uninitialized] 31 | return next==1; | ~~~~^~~
ソースコード
#include <bits/stdc++.h>using namespace std;#define reep(i,a,b) for(int i=(a);i<(b);i++)#define rep(i,n) reep(i,0,(n))typedef long long ll;__int128 bigIntMillerRabinSuspectPow(int a, __int128 k, __int128 n){__int128 p=1;__int128 bit=0x80000000U;for(bit=bit*bit*0x40000000U;bit;bit>>=1){if(p>1) p=(p*p)%n;if(k&bit) p=(p*a)%n;}return p;}int bigIntMillerRabinSuspect(int b, __int128 n){__int128 i,t=0,u=n-1;__int128 now,next;while(!(u&1)) t++,u>>=1;now = bigIntMillerRabinSuspectPow(b, u, n);for(i=1;i<=t;i++){next=(now*now)%n;if(next==1 && now!=1 && now!=n-1) return 0;now=next;}return next==1;}int bigIntMillerRabin(__int128 n){if(n<=1) return 0;if(n<=3) return 1;if(!(n&1)) return 0;if(!bigIntMillerRabinSuspect(2,n)) return 0;for(int i=3;i<=51;i+=2) if(!bigIntMillerRabinSuspect(i,n)) return 0;return 1;}bool prime[100000];int main(){string s;cin>>s;__int128 n=0;rep(i,s.size()){n*=10;n+=s[i]-'0';}if(n<10000){reep(i,2,100000) prime[i]=true;for(int i=2;i*i<=100000;i++){if(prime[i]){for(int j=i*i;j<100000;j+=i){prime[j]=false;}}}ll m=n;reep(i,2,m){queue<int> q;q.push(1);vector<bool> used(m+1);used[1]=true;while(q.size()){int top=q.front();q.pop();// top+1 top-1 top+i top-iint next = top+1;if(next<=m&&top%i!=0&&!prime[next]&&!used[next]) q.push(next),used[next]=true;next = top-1;if(0<next&&top%i!=1&&!prime[next]&&!used[next]) q.push(next),used[next]=true;next = top+i;if(next<=m&&!prime[next]&&!used[next]) q.push(next),used[next]=true;next = top-i;if(0<next&&!prime[next]&&!used[next]) q.push(next),used[next]=true;}if(used[m]){cout<<i<<endl;return 0;}}}else{if(bigIntMillerRabin(n-8)&&n%8==1){cout<<14<<endl;}else{cout<<8<<endl;}}}