結果
問題 |
No.308 素数は通れません
|
ユーザー |
![]() |
提出日時 | 2015-12-01 08:56:56 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 6 ms / 1,000 ms |
コード長 | 1,860 bytes |
コンパイル時間 | 714 ms |
コンパイル使用メモリ | 68,400 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-27 18:08:46 |
合計ジャッジ時間 | 2,714 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 107 |
ソースコード
#include <iostream> #include <set> #include <vector> #include <cassert> using namespace std; typedef __int128 Int; Int mulMod(Int x, Int k, Int m) { if (k == 0) return 0; if (k % 2 == 0) return mulMod((x+x) % m, k/2, m); else return (x+mulMod(x, k-1, m)) % m; } Int powMod(Int x, Int k, Int m) { if (k == 0) return 1; if (k % 2 == 0) return powMod(mulMod(x, x, m) % m, k/2, m); else return mulMod(x, powMod(x, k-1, m), m); } bool suspect(Int a, int s, Int d, Int n) { Int x = powMod(a, d, n); if (x == 1) return true; for (int r = 0; r < s; ++r) { if (x == n - 1) return true; x = mulMod(x, x, n); } return false; } bool isPrime(Int n) { if (n <= 1 || (n > 2 && n % 2 == 0)) return false; int test[] = {2,3,5,7,11,13,17,19,23,27,29,31,-1}; Int d = n - 1, s = 0; while (d % 2 == 0) ++s, d /= 2; for (int i = 0; test[i] < n && test[i] != -1; ++i) if (!suspect(test[i], s, d, n)) return false; return true; } vector<int> eratosthenes_sieve(int n){ vector<int> res(n+1); if(n<2) return res; res[2]=1; for(int i=3;i<=n;i+=2){ if(i*i<=n && !res[i]) for(int j=i+i+i;j<=n;j+=i+i) res[j]=1; res[i]=!res[i]; } return res; } string s; Int n; vector<int> p; int solve_naive(Int n){ for(int i=3;;i++){ vector<int> ok(2*n); ok[0] = 1; for(int _=5;_--;)for(int j=0;j<n;j++)if(ok[j] && !p[j+1]){ if(j/i == (j+1)/i) ok[j+1] = 1; if(j>=i) ok[j-i] = 1; if(j%i) ok[j-1] = 1; ok[j+i] = 1; } if(ok[n-1]){ return i; } } } int solve(Int n){ return (n % 8 != 1) || !isPrime(n - 8) ? 8 : 14; } int main(int argc, char *argv[]){ p = eratosthenes_sieve(4000); cin >> s; for(char c : s) n = n*10 + c - '0'; cout << (n < 3000 ? solve_naive(n) : solve(n)) << endl; return 0; }