結果
問題 |
No.368 LCM of K-products
|
ユーザー |
![]() |
提出日時 | 2016-05-03 23:17:23 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 328 ms / 2,000 ms |
コード長 | 1,613 bytes |
コンパイル時間 | 1,080 ms |
コンパイル使用メモリ | 109,688 KB |
実行使用メモリ | 19,840 KB |
最終ジャッジ日時 | 2024-09-22 14:45:23 |
合計ジャッジ時間 | 4,973 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 35 |
ソースコード
#include <algorithm> #include <numeric> #include <string> #include <vector> #include <iostream> #include <queue> #include <utility> #include <cmath> #include <map> #include <unordered_map> #include <functional> #include <fstream> using namespace std; using ull = unsigned long long; const ull MOD = static_cast<ull>(1e9+7); int main() { ull n,k; cin >> n >> k; vector<ull> a(n); map<ull,vector<ull>> dic; for(int i =0; i < n; ++i) { cin >> a.at(i); ull tmp = a.at(i); int j = 2; while(j*j <= a.at(i)) { if(tmp % j ==0) { vector<ull> t(n,0); tmp /= j; if(dic.find(j) != dic.end()) { dic.at(j).at(i) +=1; } else { dic.emplace(j,t); dic.at(j).at(i) = 1; } } else { ++j; } } vector<ull> t(n,0); if(dic.find(tmp) != dic.end()) { dic.at(tmp).at(i) +=1; } else { dic.emplace(tmp,t); dic.at(tmp).at(i) = 1; } } ull sum = 1; for(auto&& x : dic) { sort(x.second.begin(),x.second.end(),greater<ull>()); ull count = 0; for(int i =0; i < k ; ++i) { count += x.second.at(i); } for(int i =0; i < count; ++i) { sum = (sum*x.first) % MOD; } } cout << sum << endl; }