結果
問題 | No.2365 Present of good number |
ユーザー |
👑 ![]() |
提出日時 | 2023-06-30 22:39:31 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 18 ms / 2,000 ms |
コード長 | 1,545 bytes |
コンパイル時間 | 982 ms |
コンパイル使用メモリ | 92,416 KB |
最終ジャッジ日時 | 2025-02-15 04:16:41 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 39 |
ソースコード
#include <iostream> #include <string> #include <vector> #include <algorithm> #include <map> #include <atcoder/modint> using namespace std; using i32 = int; using u32 = unsigned int; using i64 = long long; using u64 = unsigned long long; #define rep(i,n) for(int i=0; i<(int)(n); i++) const i64 INF = 1001001001001001001; using Modint = atcoder::static_modint<1000000007>; vector<int> pf(int n){ vector<int> res; for(int p=2; p*p<=n; p++){ while(n%p == 0){ res.push_back(p); n /= p; } } if(n != 1) res.push_back(n); return res; } int main(){ i64 N, K; cin >> N >> K; map<int, i64> mp; for(int x : pf(N)) mp[x] += 1; while(K){ if(mp.size() == mp.count(2) + mp.count(3)) break; K--; map<int, i64> buf; for(auto [p,c] : mp) for(int q : pf(p+1)) buf[q] += c; for(auto& q : buf) q.second %= 1000000006; swap(mp, buf); } if(K == 0){ Modint ans = 1; for(auto [p,c] : mp) ans *= Modint(p).pow(c); cout << ans.val(); } else{ i64 q = atcoder::static_modint<1000000006>(2).pow(K/2).val(); K %= 2; if(K % 2 == 0){ auto q2 = Modint(2).pow(mp[2]).pow(q); auto q3 = Modint(3).pow(mp[3]).pow(q); cout << (q2 * q3).val() << endl; } else{ auto q2 = Modint(2).pow(mp[3]).pow(q*2); auto q3 = Modint(3).pow(mp[2]).pow(q); cout << (q2 * q3).val() << endl; } } return 0; }