結果
問題 |
No.368 LCM of K-products
|
ユーザー |
|
提出日時 | 2022-04-23 16:36:23 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 98 ms / 2,000 ms |
コード長 | 1,040 bytes |
コンパイル時間 | 4,283 ms |
コンパイル使用メモリ | 237,480 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-25 03:48:08 |
合計ジャッジ時間 | 5,437 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 35 |
コンパイルメッセージ
main.cpp: In function 'int main()': main.cpp:33:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions] 33 | for (auto [p, cnt] : mp) { | ^
ソースコード
#include <bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; using ll = long long; using vi = vector<int>; using vvi = vector<vector<int>>; using pii = pair<int, int>; #define rep(i, n) for (int i = 0; i < (int)(n); ++i) #define repr(i, n) for (int i = (int)(n - 1); i >= 0; --i) using mint = modint1000000007; int main() { int n, k; cin >> n >> k; vi a(n); rep(i, n) cin >> a[i]; map<int, vi> mp; for (int x : a) { for (int k = 2; k * k <= x; k++) { if (x % k == 0) { int c = 0; while (x % k == 0) { x /= k; c++; } mp[k].push_back(c); } } if (x > 0) mp[x].push_back(1); } mint r = 1; for (auto [p, cnt] : mp) { sort(cnt.begin(), cnt.end(), greater<int>()); int m = 0; rep(i, min(k, (int)cnt.size())) m += cnt[i]; r *= mint(p).pow(m); } cout << r.val() << endl; return 0; }