結果
問題 | No.12 限定された素数 |
ユーザー |
![]() |
提出日時 | 2014-11-16 05:43:10 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 36 ms / 5,000 ms |
コード長 | 1,347 bytes |
コンパイル時間 | 533 ms |
コンパイル使用メモリ | 61,800 KB |
実行使用メモリ | 11,564 KB |
最終ジャッジ日時 | 2024-11-24 07:34:12 |
合計ジャッジ時間 | 2,215 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:38:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 38 | scanf("%d", &N); | ~~~~~^~~~~~~~~~ main.cpp:40:27: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 40 | REP(i, N){int a; scanf("%d", &a); restricted |= 1 << a;} | ~~~~~^~~~~~~~~~
ソースコード
#include <cstdio> #include <iostream> #include <vector> #define FOR(i,a,b) for(int i=(a);i<(b);i++) #define REP(i,j) FOR(i,0,j) typedef long long ll; std::vector<int> primes; bool isPrime[5000101]; int xs[348518]; int N, A[10]; int main(){ std::fill(isPrime, isPrime+5000101, true); std::fill(&xs[0], &xs[0]+348518, 0); primes.push_back(0); primes.push_back(2); xs[1] = 0x4; for(int i=4;i<=5000100;i+=2){isPrime[i] = false;} int length = 2; for(ll i=3;i<=5000100;i+=2){ if(isPrime[i]){ primes.push_back(i); int x = i; while(x > 0){xs[length] |= 1 << (x % 10); x /= 10;} length += 1; for(ll j=i*i;j<=5000100ll;j+=i){ isPrime[j] = false; } } } scanf("%d", &N); int restricted = 0; REP(i, N){int a; scanf("%d", &a); restricted |= 1 << a;} int res = -1; for(int i=1,j=1;i<348514;){ int y = 0; while(j < 348514 && (~restricted & xs[j]) == 0){ y |= xs[j]; j += 1; } if(y == restricted){ res = std::max(res, std::min(primes[j],5000001)-primes[i-1]-2); } i = j+1; j = i; } printf("%d\n", res); }