結果
問題 |
No.3127 Multiple of Twin Prime
|
ユーザー |
![]() |
提出日時 | 2025-04-26 02:15:26 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 281 ms / 2,500 ms |
コード長 | 1,374 bytes |
コンパイル時間 | 6,044 ms |
コンパイル使用メモリ | 333,632 KB |
実行使用メモリ | 10,540 KB |
最終ジャッジ日時 | 2025-04-26 02:15:37 |
合計ジャッジ時間 | 10,871 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 12 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using i32 = int; using u32 = unsigned int; using i64 = long long; using u64 = unsigned long long; #define FAST_IO \ ios::sync_with_stdio(false); \ cin.tie(0); const i64 INF = 1001001001001001001; using Modint = atcoder::static_modint<998244353>; vector<int> get_primes(int n) { vector<int> res; vector<bool> is_prime(n + 1, true); for (int i = 2; i <= n; i ++) { if (is_prime[i]) { res.push_back(i); for (int j = i + i; j <= n; j += i) { is_prime[j] = false; } } } return res; } vector<pair<i64, i64>> twin_primes(int n) { vector<pair<i64, i64>> res; vector<int> primes = get_primes(n); for (int i = 0; i < primes.size() - 1; i ++) { if (primes[i + 1] - primes[i] == 2) { res.emplace_back(primes[i], primes[i + 1]); } } return res; } int main() { FAST_IO auto tp = twin_primes(1e7 + 1000); int T; cin >> T; for (int i = 0; i < T; i ++) { i64 N; cin >> N; int ok = -1; int ng = tp.size(); while (ng - ok > 1) { int mid = (ok + ng) / 2; if (tp[mid].first * tp[mid].second <= N) { ok = mid; } else { ng = mid; } } if (ok == -1) { cout << -1 << endl; continue; } cout << tp[ok].first * tp[ok].second << endl; } }