結果
問題 | No.12 限定された素数 |
ユーザー |
![]() |
提出日時 | 2015-12-13 20:54:54 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 112 ms / 5,000 ms |
コード長 | 1,700 bytes |
コンパイル時間 | 752 ms |
コンパイル使用メモリ | 97,032 KB |
実行使用メモリ | 25,472 KB |
最終ジャッジ日時 | 2024-11-24 08:32:58 |
合計ジャッジ時間 | 4,471 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
#include <iostream> #include <vector> #include <array> #include <algorithm> #include <string> #include <map> #include <queue> #include <iomanip> #include <numeric> #include <memory> #include <limits.h> #include <set> #include <cassert> #include <cmath> #include <bitset> #include <functional> #include <limits> using namespace std; typedef long long ll; typedef unsigned long long ull; #define REP(i,n) for(ll i=0; i<(n); ++i) #define TEN(x) ((ll)1e##x) #define ALL(v) (v).begin(), (v).end() // エラトステネスのふるい O(n log log n) : t[i] = true ⇔ iが素数 (i <= n) vector<int> sieve_of_eratosthenes(ll n) { vector<int> t(n+1, true); t[0] = t[1] = false; for(ll i = 2; i <= n; ++i) if (t[i]){ for(ll j = 2*i; j <= n; j += i) t[j] = false; } return t; } vector<ll> get_occur_list(ll x) { vector<ll> occur(10, 0); while (x!=0) { occur[x % 10]++; x /= 10; } return occur; } int main(){ vector<bool> a(10, false); ll n; cin >> n; REP(_, n) { ll i; cin >> i; a[i] = true; } vector<ll> p; p.reserve(5000000); { auto t = sieve_of_eratosthenes(5000000); REP(i, t.size()) if (t[i]) p.push_back(i); } ll max_interval = -1; vector<ll> occur(10, 0); ll end = -1; REP(i, p.size()) { auto _ = get_occur_list(p[i]); REP(j, 10) occur[j] += _[j]; REP(j, 10) if(!a[j]) while(occur[j]!=0){ end++; auto _ = get_occur_list(p[end]); REP(k, 10) occur[k] -= _[k]; } bool valid = true; REP(j, 10) if (a[j]) if (occur[j] == 0) valid = false; if (valid) { ll k = (end == -1) ? 1 : p[end] + 1 ; ll l = (i == p.size() - 1) ? 5000000 : p[i+1] - 1 ; max_interval = max(max_interval, l - k); } } cout << max_interval << endl; return 0; }