結果
問題 | No.2365 Present of good number |
ユーザー |
|
提出日時 | 2021-07-02 22:51:50 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
MLE
|
実行時間 | - |
コード長 | 1,088 bytes |
コンパイル時間 | 1,226 ms |
コンパイル使用メモリ | 166,916 KB |
実行使用メモリ | 813,952 KB |
最終ジャッジ日時 | 2024-07-07 08:27:01 |
合計ジャッジ時間 | 2,856 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | MLE * 1 -- * 38 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;ll m = 1e9 + 7;ll max_p[100010];ll mpow(ll md, ll x, ll n) {ll ret = 1;while (n) {if (n % 2) {ret *= x;ret %= md;}x = (x * x) % md;n /= 2;}return ret;}ll calc_ans(ll N, ll K) {if (K == 0) {return N;}if (N == 2) {if (K % 2) {return mpow(m, 3, mpow(m - 2, 2, K / 2));} else {return mpow(m, 2, mpow(m - 2, 2, K / 2));}}ll ret = 1;while (N > 1) {ret *= calc_ans(max_p[(int)N] + 1, K - 1);N /= max_p[(int)N];}return ret;}int main () {max_p[0] = max_p[1] = 1;for (int i = 2; i <= 100000; i ++) {max_p[i] = -1;}for (int i = 2; i <= 100000; i ++) {if (max_p[i] == -1) {max_p[i] = i;for (int j = 2; j * i <= 100000; j ++) {max_p[i * j] = i;}}}ll N, K;cin >> N >> K;cout << calc_ans(N, K) << endl;}