結果
問題 |
No.368 LCM of K-products
|
ユーザー |
![]() |
提出日時 | 2016-06-19 01:44:48 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 145 ms / 2,000 ms |
コード長 | 627 bytes |
コンパイル時間 | 1,738 ms |
コンパイル使用メモリ | 178,004 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-22 14:50:13 |
合計ジャッジ時間 | 3,066 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 35 |
ソースコード
#include <bits/stdc++.h> using namespace std; const int mod=1e9+7; int main(){ int n,k; cin>>n>>k; map<int,multiset<int>> mp; for(int i=0;i<n;i++){ int a; cin>>a; for(int j=2;a>1&&j*j<=a;j++){ int add=0; while(a%j==0){ add++; a/=j; } if(add) mp[j].insert(add); } if(a) mp[a].insert(1); } long long ans=1; for(auto i:mp){ auto it=i.second; int cnt=0; int p=0; for(auto j=it.rbegin();j!=it.rend();j++){ p+=*j; cnt++; if(cnt==k) break; } long long multi=i.first; while(p){ if(p&1) (ans*=multi)%=mod; (multi*=multi)%=mod; p/=2; } } cout<<ans<<endl; return 0; }