結果
問題 | No.2365 Present of good number |
ユーザー |
|
提出日時 | 2023-07-07 14:20:09 |
言語 | D (dmd 2.109.1) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,308 bytes |
コンパイル時間 | 5,107 ms |
コンパイル使用メモリ | 172,344 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-21 09:30:15 |
合計ジャッジ時間 | 6,638 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 1 |
other | AC * 1 WA * 38 |
ソースコード
import std;void read(T...)(string S, ref T args) {auto buf = S.split;foreach (i, ref arg; args) {arg = buf[i].to!(typeof(arg));}}void main () {//*long N, K; readln.read(N, K);solve(N, K);// *//* testforeach (N; 2..100001) {solve(N, -1);}// */}void solve (long N, long K) {const MOD = 100_000_000_7;long powOf2 = 0;long powOf3 = 0;while (true) {// break条件if (N == 1 || K == 0) {break;}// 2冪3冪だけの処理long tmp = powOf2;powOf2 = 2*powOf3;powOf3 = tmp;N = f(N, powOf2, powOf3);K--;}long ans = 0;// 復元+出力if (K == 0) {ans = N % MOD;ans *= modpow(2, powOf2);ans %= MOD;ans *= modpow(3, powOf3);ans %= MOD;writeln(ans);return;}// 残りのKを処理 2手で指数が全部二倍になるwriteln(powOf2, powOf3);// 一回進めるif (K % 2 == 1) {long tmp = powOf2;powOf2 = 2*powOf3;powOf3 = tmp;K--;}ans = modpow(2, modpow(2, K/2, MOD-2) * powOf2 % (MOD-2)) * modpow(3, modpow(2, K/2, MOD-2) * powOf3 % (MOD-2));ans %= MOD;writeln(ans);}long modpow (long a, long x, const long MOD = 100_000_000_7) {assert(0 <= a);assert(0 <= x);// base caseif (x == 0) {return 1;}if (x == 1) {return a % MOD;}// recursive caseif (x % 2 == 0) {auto res = modpow(a, x/2);return res*res % MOD;} else {return modpow(a, x-1);}}long f (long A, ref long powOf2, ref long powOf3) {auto x = Factors(A);long res = 1;foreach (i; 0..x.factor.length) {if (x.factor[i] == 1) {continue;}if (x.factor[i] == 2) {powOf3 += x.pow[i];} else if (x.factor[i] == 3) {powOf2 += 2 * x.pow[i];} else {res *= (x.factor[i] + 1) ^^ x.pow[i];}}return res;}struct Factors {long target;long[] factor;long[] pow;bool is_prime () {if (target <= 0) {return false;}if (factor.length == 2 && pow[1] == 1) {return true;}return false;}long[] combine_factor () {if (target <= 0) {return [];}long[] ret;foreach (i, x; pow) {foreach (k; 0..x) {ret ~= factor[i];}}return ret;}this (long target_) {{ // check inputassert(0 < target_);}target = target_;factor = [];pow = [];pow ~= 1;factor ~= 1;foreach (i; 2..target_) {if (target_ < i*i) {break;}if (target_ % i == 0) {factor ~= i;pow ~= 0;while (target_ % i == 0) {target_ /= i;pow[$-1]++;}}}if (target_ != 1) {factor ~= target_;pow ~= 1;}}}