結果
問題 |
No.6 使いものにならないハッシュ
|
ユーザー |
|
提出日時 | 2024-10-20 21:04:22 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4 ms / 5,000 ms |
コード長 | 852 bytes |
コンパイル時間 | 2,044 ms |
コンパイル使用メモリ | 198,424 KB |
最終ジャッジ日時 | 2025-02-24 21:58:22 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main(){ cin.tie(nullptr)->sync_with_stdio(false); int L, R; cin >> L >> R; vector<int> P, is_P(R + 1, 1); is_P[0] = is_P[1] = 0; for(long long i = 2; i <= R; ++i){ if(is_P[i]){ if(L <= i && i <= R) P.emplace_back(i); for(long long j = i * i; j <= R; j += i){ is_P[j] = 0; } } } const int N = P.size(); vector<int> H(N); for(int i = 0; i < N; ++i){ int x = P[i]; while(!(x < 10)){ string s = to_string(x); x = 0; for(char c: s) x += c - '0'; } H[i] = x; } int ans = 0, fir = -1; vector<int> cnt(10); for(int L = 0, R = 0; L < N; ++L){ while(R < N && cnt[H[R]] == 0) ++cnt[H[R++]]; if(ans <= R - L){ ans = R - L; fir = P[L]; } cnt[H[L]]--; } cout << fir << endl; return 0; }