結果
問題 |
No.368 LCM of K-products
|
ユーザー |
|
提出日時 | 2024-08-18 21:35:55 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 310 ms / 2,000 ms |
コード長 | 1,187 bytes |
コンパイル時間 | 1,828 ms |
コンパイル使用メモリ | 186,056 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-08-18 21:35:59 |
合計ジャッジ時間 | 3,970 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 35 |
ソースコード
# include <bits/stdc++.h> using namespace std; typedef long long ll; # define int long long # define lc u << 1 # define rc u << 1 | 1 # define fi first # define se second const int mod = 1e9 + 7; int n, k; map <int, vector <int>> fac; int quick_pow (int a, int b = mod - 2) { int ans = 1; while (b) { if (b & 1) ans = ans * a % mod; a = a * a % mod; b >>= 1; } return ans; } signed main () { int i,j,k,l,r,x,y; string s; scanf ("%d%d", &n, &k); for (int i = 1; i <= n; i ++ ) { int x; scanf ("%d", &x); map <int, int> mp; for (int i = 2; i * i <= x; i ++ ) { while (x % i == 0) { mp[i] ++ ; x /= i; } } if (x > 1) mp[x] ++ ; for (auto t : mp) fac[t.fi].push_back (t.se); } int ans = 1; for (auto t : fac) { auto vec = t.se; sort (vec.begin (), vec.end (), greater <int> ()); int sum = 0; for (int i = 0; i <= min (k - 1, (int)vec.size () - 1); i ++ ) sum += vec[i]; ans = ans * quick_pow (t.fi, sum) % mod; } printf ("%d\n", ans); return 0; }