結果

問題 No.371 ぼく悪いプライムじゃないよ
ユーザー kenkooookenkoooo
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

/*
_ooOoo_
o8888888o
88" . "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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0