結果
問題 |
No.368 LCM of K-products
|
ユーザー |
|
提出日時 | 2021-05-23 04:52:31 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 53 ms / 2,000 ms |
コード長 | 2,345 bytes |
コンパイル時間 | 2,163 ms |
コンパイル使用メモリ | 213,004 KB |
最終ジャッジ日時 | 2025-01-21 17:32:21 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 35 |
ソースコード
#include <bits/stdc++.h> using namespace std; const long long int MOD = 1e9 + 7; map <int, int> cnt[1001]; vector <int> prime; void eratos() { bool isprime[31623]; memset(isprime, true, sizeof(isprime)); for (int j = 2; j <= 31622; j++) { if (isprime[j]) { prime.push_back(j); for (int k = 2 * j; k <= 31622; k += j) { isprime[k] = false; } } } } long long int mypow(long long int x, long long int n) { long long int res = 1; while (n > 0) { if (n % 2 == 1) { res = ((res % MOD) * (x % MOD) % MOD); res %= MOD; } x = ((x % MOD) * (x % MOD) % MOD); x %= MOD; n /= 2; } return res; } int main(void) { cin.tie(0); ios::sync_with_stdio(false); int n, k, t; vector <int> v; set <int> s; cin >> n >> k; for (int i = 0; i < n; i++) { cin >> t; v.push_back(t); } eratos(); for (int i = 0; i < n; i++) { long long int val = v[i]; for (int j = 0; j < prime.size(); j++) { if (val == 1 || val < prime[j] * prime[j]) { break; } if (val % prime[j] == 0) { s.insert(prime[j]); while (1) { if (val % prime[j] != 0) { break; } cnt[i][prime[j]]++; val /= prime[j]; } } } if (val != 1) { s.insert(val); cnt[i][val] += 1; } } long long int res = 1; for (auto it : s) { vector <int> v; for (int i = 0; i < n; i++) { if (cnt[i].find(it) == cnt[i].end()) { v.push_back(0); } else { v.push_back(cnt[i][it]); } } sort(v.rbegin(), v.rend()); int sum = 0; for (int i = 0; i < k; i++) { sum += v[i]; } res = ((res % MOD) * (mypow(it, sum) % MOD) % MOD); res %= MOD; } cout << res << '\n'; return 0; }