結果
問題 | No.371 ぼく悪いプライムじゃないよ |
ユーザー |
![]() |
提出日時 | 2016-05-13 23:58:09 |
言語 | C++11 (gcc 13.3.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,330 bytes |
コンパイル時間 | 1,360 ms |
コンパイル使用メモリ | 164,304 KB |
実行使用メモリ | 13,636 KB |
最終ジャッジ日時 | 2024-10-05 18:37:46 |
合計ジャッジ時間 | 4,347 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 20 WA * 2 TLE * 1 -- * 19 |
ソースコード
/*_ooOoo_o8888888o88" . "88(| -_- |)O\ = /O____/`---'\____.' \\| |// `./ \\||| : |||// \/ _||||| -:- |||||- \| | \\\ - /// | || \_| ''\---/'' | |\ .-\__ `-` ___/-. /___`. .' /--.--\ `. . __."" '< `.___\_<|>_/___.' >'"".| | : `- \`.;`\ _ /`;.`/ - ` : | |\ \ `-. \_ __\ /__ _/ .-` / /======`-.____`-.___\_____/___.-`____.-'======`=---='^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^pass System Test!*/#include <bits/stdc++.h>using namespace std;template <typename T>std::ostream &operator<<(std::ostream &out, const std::vector<T> &v) {if (!v.empty()) {out << '[';std::copy(v.begin(), v.end(), std::ostream_iterator<T>(out, ", "));out << "\b\b]";}return out;}template <typename T1, typename T2>std::ostream &operator<<(std::ostream &out, const std::pair<T1, T2> &p) {out << "[" << p.first << ", " << p.second << "]";return out;}template <class T, class U>void chmin(T &t, U f) {if (t > f) t = f;}template <class T, class U>void chmax(T &t, U f) {if (t < f) t = f;}template <typename T>void uniq(vector<T> &v) {v.erase(unique(v.begin(), v.end()), v.end());}vector<int> eratosthenes(int N) {vector<bool> is_prime(N + 1, true);vector<int> primes;is_prime[0] = false;is_prime[1] = false;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;}}return primes;}int64_t L, H;vector<int> primes;int N;int64_t dfs_check(int64_t d, int pos) {int64_t ans = -1;if (L <= d && d <= H) ans = d;for (int i = pos; i < N; ++i) {if (d * primes[i] > H) break;chmax(ans, dfs_check(d * primes[i], i));}return ans;}int main() {cin.tie(0);ios::sync_with_stdio(false);primes = eratosthenes(1e5);N = primes.size();cin >> L >> H;int64_t ans = 0;for (int i = N - 1; i >= 0; --i) {int64_t d = dfs_check(primes[i], i);if (d > primes[i]) {ans = d;break;}}assert(ans > 0);cout << ans << endl;}