結果
問題 |
No.368 LCM of K-products
|
ユーザー |
|
提出日時 | 2024-12-24 13:12:14 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 103 ms / 2,000 ms |
コード長 | 1,031 bytes |
コンパイル時間 | 6,622 ms |
コンパイル使用メモリ | 325,112 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-24 13:12:23 |
合計ジャッジ時間 | 8,277 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 35 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; #define rep(i, n) for (int i = 0; i < (n); ++i) using namespace std; using P = pair<int, int>; using mint = modint1000000007; vector<P> factorize(int n) { vector<P> res; for (int i = 2; i*i <= n; ++i) { if (n%i != 0) continue; res.emplace_back(i, 0); while (n%i == 0) { n /= i; res.back().second++; } } if (n != 1) res.emplace_back(n, 1); return res; } int main() { int n, k; cin >> n >> k; map<int, vector<int>> mp; rep(i, n) { int a; cin >> a; auto fs = factorize(a); for (auto [p, x] : fs) mp[p].push_back(x); } mint ans = 1; for (auto [p, xs] : mp) { auto d = xs; ranges::sort(d, greater<>()); if (d.size() > k) d.resize(k); int cnt = 0; rep(i, d.size()) cnt += d[i]; ans *= mint(p).pow(cnt); } cout << ans.val() << '\n'; return 0; }