結果
問題 | No.2425 Power Range GCD |
ユーザー |
![]() |
提出日時 | 2023-08-18 23:34:14 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 81 ms / 2,000 ms |
コード長 | 1,318 bytes |
コンパイル時間 | 1,050 ms |
コンパイル使用メモリ | 83,848 KB |
実行使用メモリ | 18,944 KB |
最終ジャッジ日時 | 2024-11-28 11:03:28 |
合計ジャッジ時間 | 3,191 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 31 |
ソースコード
#include <iostream>#include <vector>#include <algorithm>#include <set>using namespace std;using P = pair<int, int>;int main(){int l, r; cin >> l >> r;const int lim = 2000000;vector<int> isprime(lim);for(int i = 0; i < lim; i++) isprime[i] = i;for(int i = 2; i < lim; i++){if(isprime[i] != i) continue;for(int j = i+i; j < lim; j += i) isprime[j] = min(isprime[j], i);}vector<int> cnt(lim, 0);set<int> mem;{int x = l;while(x > 1){cnt[isprime[x]]++;mem.emplace(isprime[x]);x /= isprime[x];}for(int i = 0; i < lim; i++) cnt[i] *= l;}for(int i = l+1; i <= r; i++){int x = i;vector<int> facs;while(x > 1){int p = isprime[x];facs.emplace_back(p);mem.erase(p);int z = 0;while(x%p == 0){x /= p;z++;}cnt[p] = min(cnt[p], z*i);}for(auto &it: mem) cnt[it] = 0;mem.clear();for(auto &it: facs) mem.emplace(it);}long long ans = 1;for(auto &i: mem){for(int j = 0; j < cnt[i]; j++){ans *= i;}}cout << ans << endl;return 0;}