結果
問題 | No.371 ぼく悪いプライムじゃないよ |
ユーザー |
|
提出日時 | 2016-05-13 23:03:47 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,132 bytes |
コンパイル時間 | 1,991 ms |
コンパイル使用メモリ | 165,324 KB |
実行使用メモリ | 10,496 KB |
最終ジャッジ日時 | 2024-12-30 18:01:29 |
合計ジャッジ時間 | 5,149 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 41 TLE * 1 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { long long L, H; cin >> L >> H; const int N = 1e5 + 100; vector<long long> primes; vector<char> is_prime(N, true); for (int i = 2; i < N; i++) { if (is_prime[i]) { primes.push_back(i); for (int j = i * 2; j < N; j += i) { is_prime[j] = false; } } } if (H - L <= 100000) { pair<long long, long long> ans; for (long long i = L; i <= H; i++) { long long p = 1; for (long long j = 2; j * j <= i; j++) { if (i % j == 0) { p = j; break; } } if (p != 1) ans = max(ans, make_pair(p, i)); } cout << ans.second << endl; return 0; } vector<vector<long long>> dp(40); dp[0].push_back(1); for (int i = primes.size() - 1; i >= 0; i--) { for (int j = 0; j < 39; j++) { for (long long x : dp[j]) { if (x * primes[i] <= H) { dp[j + 1].push_back(x * primes[i]); } } } long long ans = 0; for (int j = 2; j < 39; j++) { for (long long x : dp[j]) { if (L <= x && x <= H) ans = max(ans, x); } } if (ans != 0) { cout << ans << endl; return 0; } } cout << "fail" << endl; }