結果
問題 | No.6 使いものにならないハッシュ |
ユーザー |
![]() |
提出日時 | 2020-12-26 16:51:28 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 7 ms / 5,000 ms |
コード長 | 1,271 bytes |
コンパイル時間 | 2,055 ms |
コンパイル使用メモリ | 205,408 KB |
最終ジャッジ日時 | 2025-01-17 07:30:29 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 |
ソースコード
#include <bits/stdc++.h>using namespace std;// エラトステネスの篩(nは1以上, 素数列挙のみならi*i<=nで良い) O(nloglogn)vector<bool> sieve(int n) {vector<bool> x(n + 1, true);x.at(0) = x.at(1) = false;for (int i = 2; i <= n; i++) {if (x.at(i)) {for (int j = 2 * i; j <= n; j += i) x.at(j) = false;}}return x;}// 各桁の数の和int digitSum(int x) {int sum = 0;while (x > 0) {sum += x % 10;x /= 10;}if (sum <= 9) return sum;else return digitSum(sum);}int main() {cin.tie(0);ios::sync_with_stdio(false);int k, n;cin >> k >> n;vector<bool> p = sieve(n);vector<int> primes;for (int i = k; i <= n; i++) {if (p[i]) primes.emplace_back(i);}vector<int> hash(primes.size());for (int i = 0; i < primes.size(); i++) hash[i] = digitSum(primes[i]);int ans = -1, len = 0, it = 0;set<int> s;for (int i = 0; i < hash.size(); i++) {while (true) {if (it < hash.size() && s.find(hash[it]) == s.end()) {s.insert(hash[it]);it++;}else {break;}}if (it - i >= len){len = max(len, it - i);ans = primes[i];}s.erase(hash[i]);}cout << ans << '\n';}