結果
問題 | No.2365 Present of good number |
ユーザー |
![]() |
提出日時 | 2023-06-30 22:11:45 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,341 bytes |
コンパイル時間 | 2,422 ms |
コンパイル使用メモリ | 207,984 KB |
最終ジャッジ日時 | 2025-02-15 04:00:43 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 1 WA * 38 |
ソースコード
#include <bits/stdc++.h>using namespace std;#ifdef LOCAL#include "settings/debug.cpp"#define _GLIBCXX_DEBUG#else#define Debug(...) void(0)#endifusing ll = long long;#define rep(i, n) for (int i = 0; i < (n); ++i)#include <atcoder/modint>using mint = atcoder::modint1000000007;int main() {ll n, k;cin >> n >> k;vector<pair<ll, ll>> pf(0);for (int i = 2; i * i <= n; ++i) {if (n % i == 0) {pf.push_back({ i, 0 });while (n % i == 0) {n /= i;pf.back().second++;}}}if (n > 1) pf.push_back({ n, 1 });while (pf.size() > 2 && k > 0) {--k;map<ll, ll> new_pf;new_pf[2] = new_pf[3] = 0;for (auto [p, e] : pf) {if (p == 2)new_pf[3] += e;else if (p == 3)new_pf[2] += 2 * e;else {assert(p % 2 == 1);ll new_p = p + 1;while (new_p % 2 == 0) {new_p /= 2;new_pf[2] += e;}assert(new_p % 2 == 1);if (new_p != 1) {new_pf[new_p] += e;}}}pf.clear();for (auto [p, e] : new_pf) {pf.push_back({ p, e });}Debug(k, pf);}mint ans = 1;for (auto [p, e] : pf) {ans *= mint(p + (k % p)).pow((mint(e) * mint(2).pow(k / p)).val());}cout << ans.val() << endl;return 0;}