結果
問題 |
No.6 使いものにならないハッシュ
|
ユーザー |
![]() |
提出日時 | 2018-12-30 15:40:14 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 5 ms / 5,000 ms |
コード長 | 1,748 bytes |
コンパイル時間 | 957 ms |
コンパイル使用メモリ | 98,724 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-16 16:45:14 |
合計ジャッジ時間 | 1,969 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 |
ソースコード
#include <iostream> #include <string> #include <vector> #include <set> #include <cmath> #include <stack> #include <algorithm> #include <iomanip> #include <map> #include <queue> #include <functional> #include <numeric> using ll = long long; using namespace std; const ll MOD = 1e9 + 7; vector<int> prime; bool sieve[200010]; int key[100010]; int Hash[55]; int main(void) { int K, N; cin >> K >> N; for (int i = 0; i < 200010; ++i) sieve[i] = true; sieve[0] = sieve[1] = false; for (int i = 2; i * i < 200010; ++i) { if (sieve[i]) { for (int j = 2; i * j < 200010; ++j) { sieve[i * j] = false; } } } for (int i = K; i <= N; ++i) if (sieve[i]) prime.push_back(i); for (int i = 0; i < prime.size(); ++i) { int s = 0; string t = to_string(prime[i]); while (1) { for (int j = 0; j < t.size(); ++j) { s += t[j] - '0'; } t = to_string(s); if (t.size() == 1) break; s = 0; } key[i] = s; //cout << s << endl; } int left = 0, right = 0; int ans = 0, max_len = 0; for (left = 0; left < prime.size(); ++left) { int t = 0; while (right < prime.size() && Hash[key[right]] == 0) { Hash[key[right]]++; right++; } t = right - left; if (t >= max_len) { max_len = t; ans = max(ans, prime[left]); } if (right == left) right++; Hash[key[left]]--; } cout << ans << endl; return 0; }