結果
問題 | No.2365 Present of good number |
ユーザー |
|
提出日時 | 2023-06-30 21:44:11 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 1,072 bytes |
コンパイル時間 | 872 ms |
コンパイル使用メモリ | 85,140 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-07 09:24:37 |
合計ジャッジ時間 | 1,751 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 39 |
ソースコード
#include<iostream> #include<map> #include<cassert> #include<atcoder/modint> using namespace std; using mint=atcoder::modint1000000007; using mint1=atcoder::static_modint<(int)1e9+6>; int lsp[1<<17]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); for(int i=2;i<1<<17;i++)if(lsp[i]==0) { for(int j=i;j<1<<17;j+=i)lsp[j]=i; } int N; long long K; cin>>N>>K; map<int,mint1>fac; while(N>1) { int p=lsp[N]; N/=p; fac[p]++; } map<int,mint1>nfac; while(K) { K--; nfac.clear(); bool fn=false; for(pair<int,mint1>p:fac) { int u=p.first; if(u==2)nfac[3]+=p.second; else { u++; while(u%2==0)u/=2,nfac[2]+=p.second; while(u>1) { int v=lsp[u]; nfac[v]+=p.second; if(v>3)fn=true; u/=v; } } } fac.swap(nfac); if(!fn&&K%2==0)break; } if(K>0) { mint1 c=mint1::raw(2).pow(K/2); if(fac.find(2)!=fac.end())fac[2]*=c; if(fac.find(3)!=fac.end())fac[3]*=c; } mint ans=mint::raw(1); for(pair<int,mint1>p:fac)ans*=mint::raw(p.first).pow(p.second.val()); cout<<ans.val()<<endl; }