結果
問題 | No.2365 Present of good number |
ユーザー | shinchan |
提出日時 | 2023-06-30 22:01:01 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 534 ms / 2,000 ms |
コード長 | 2,967 bytes |
コンパイル時間 | 2,740 ms |
コンパイル使用メモリ | 222,832 KB |
実行使用メモリ | 190,616 KB |
最終ジャッジ日時 | 2023-09-21 16:00:42 |
合計ジャッジ時間 | 25,537 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 523 ms
190,336 KB |
testcase_01 | AC | 516 ms
190,564 KB |
testcase_02 | AC | 510 ms
190,512 KB |
testcase_03 | AC | 520 ms
190,364 KB |
testcase_04 | AC | 534 ms
190,364 KB |
testcase_05 | AC | 530 ms
190,552 KB |
testcase_06 | AC | 472 ms
190,324 KB |
testcase_07 | AC | 424 ms
190,416 KB |
testcase_08 | AC | 440 ms
190,336 KB |
testcase_09 | AC | 515 ms
190,328 KB |
testcase_10 | AC | 430 ms
190,560 KB |
testcase_11 | AC | 462 ms
190,364 KB |
testcase_12 | AC | 479 ms
190,616 KB |
testcase_13 | AC | 498 ms
190,472 KB |
testcase_14 | AC | 497 ms
190,464 KB |
testcase_15 | AC | 486 ms
190,420 KB |
testcase_16 | AC | 511 ms
190,488 KB |
testcase_17 | AC | 516 ms
190,424 KB |
testcase_18 | AC | 527 ms
190,556 KB |
testcase_19 | AC | 534 ms
190,360 KB |
testcase_20 | AC | 533 ms
190,568 KB |
testcase_21 | AC | 519 ms
190,564 KB |
testcase_22 | AC | 534 ms
190,548 KB |
testcase_23 | AC | 534 ms
190,520 KB |
testcase_24 | AC | 524 ms
190,440 KB |
testcase_25 | AC | 525 ms
190,336 KB |
testcase_26 | AC | 522 ms
190,328 KB |
testcase_27 | AC | 513 ms
190,540 KB |
testcase_28 | AC | 526 ms
190,336 KB |
testcase_29 | AC | 495 ms
190,328 KB |
testcase_30 | AC | 516 ms
190,568 KB |
testcase_31 | AC | 441 ms
190,444 KB |
testcase_32 | AC | 465 ms
190,464 KB |
testcase_33 | AC | 524 ms
190,328 KB |
testcase_34 | AC | 508 ms
190,416 KB |
testcase_35 | AC | 482 ms
190,492 KB |
testcase_36 | AC | 487 ms
190,576 KB |
testcase_37 | AC | 523 ms
190,604 KB |
testcase_38 | AC | 464 ms
190,600 KB |
testcase_39 | AC | 496 ms
190,604 KB |
testcase_40 | AC | 494 ms
190,480 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #define all(v) (v).begin(),(v).end() #define pb(a) push_back(a) #define rep(i, n) for(int i=0;i<n;i++) #define foa(e, v) for(auto& e : v) using ll = long long; const ll MOD7 = 1000000007, MOD998 = 998244353, INF = (1LL << 60); #define dout(a) cout<<fixed<<setprecision(10)<<a<<endl; vector<ll> p(1000001, -1); vector<pair<ll, ll>> prime(ll n) { vector<pair<ll, ll>> v; ll par = -1, num = 0; while(n != 1) { if(p[n] != par) { if(num) v.push_back({par, num}); num = 0; } par = p[n]; num ++; n /= p[n]; } if(num) v.push_back({par, num}); return v; } struct Doubling { private: std::vector<std::vector<vector<pair<ll, ll>>>> nx; public: Doubling() noexcept { nx.resize(100000, vector (63, vector<pair<ll, ll>> ())); for(ll i = 2; i < 100000; i ++) if(p[i] == i) { nx[i][0] = prime(i + 1); } for(int j = 0; j < 62; j ++) for(int i = 0; i < 100000; i ++) if(p[i] == i) { map<ll, ll> mp; for(auto [x, y] : nx[i][j]) { for(auto [x1, y1] : nx[x][j]) { mp[x1] += y * y1; mp[x1] %= MOD7 - 1; } } for(auto P : mp) { nx[i][j + 1].push_back(P); } } } vector<pair<ll, ll>> par(vector<pair<ll, ll>> now, long long m) { for(long long i = 0, j = 1; j <= m; i ++, j <<= 1) { if(m & j) { map<ll, ll> mp; for(auto [x, y] : now) { for(auto [x1, y1] : nx[x][i]) { mp[x1] += y * y1; mp[x1] %= MOD7 - 1; } } now.clear(); for(auto P : mp) { now.push_back(P); } } } return now; } }; long long modinv(long long a, long long MOD) { long long b = MOD, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b; std::swap(a, b); u -= t * v; std::swap(u, v); } u %= MOD; if (u < 0) u += MOD; return u; } long long modpow(long long a, long long n, long long MOD) { long long res = 1; a %= MOD; if(n < 0) { n = -n; a = modinv(a, MOD); } while (n > 0) { if (n & 1) res = res * a % MOD; a = a * a % MOD; n >>= 1; } return res; } int main() { cin.tie(0); ios::sync_with_stdio(false); for(ll i = 2; i <= 1000000; i ++) { if(p[i] != -1) continue; for(ll j = i; j <= 1000000; j += i) { if(p[j] == -1) p[j] = i; } } Doubling D; ll n, k; cin >> n >> k; ll ans = 1; for(auto [x, y] : D.par(prime(n), k)) { ans *= modpow(x, y, MOD7); ans %= MOD7; } cout << ans << endl; return 0; }