結果
問題 | No.2365 Present of good number |
ユーザー |
![]() |
提出日時 | 2023-07-17 06:05:01 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,124 bytes |
コンパイル時間 | 1,337 ms |
コンパイル使用メモリ | 169,120 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-09-17 21:20:55 |
合計ジャッジ時間 | 2,610 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 8 WA * 31 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define int long longusing i64 = long long;const int P = 1e9 + 7;int qpow(int b, i64 k, int p = P) {int ret = 1;while(k > 0) {if(k & 1) ret = (i64)ret * b;b = (i64)b * b;k >>= 1;}return ret;}signed main() {int n;i64 k;cin >> n >> k;int c2 = 0, c3 = 0;while(n % 2 == 0) {n /= 2;c2 ++;}while(n % 3 == 0) {n /= 3;c3 ++;}while(k > 0 && n > 1) {swap(c2, c3);(c2 *= 2);int nxtn = 1;for(int j = 2; j <= n; j ++) {int cnt = 0;while(n % j == 0) {nxtn *= j + 1;n /= j;}}n = nxtn;while(n % 2 == 0) {n /= 2;c2 ++;}while(n % 3 == 0) {n /= 3;c3 ++;}k --;}c3 = c3 * (i64)qpow(2, k - k / 2, P - 1);c2 = c2 * (i64)qpow(2, k / 2, P - 1);if(k & 1) swap(c2, c3);cout << (i64)qpow(2, c2) * qpow(3, c3) * n % P;}