結果

問題 No.2365 Present of good number
ユーザー InTheBloom
提出日時 2023-07-10 17:05:14
言語 D
(dmd 2.109.1)
結果
WA  
実行時間 -
コード長 3,302 bytes
コンパイル時間 2,801 ms
コンパイル使用メモリ 172,072 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-09-12 23:41:26
合計ジャッジ時間 3,790 ms
ジャッジサーバーID
(参考情報)
judge2 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 1 WA * 38
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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);
// */
/* test
foreach (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;
}
// 23
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, MOD);
ans %= MOD;
ans *= modpow(3, powOf3, MOD);
ans %= MOD;
writeln(ans);
return;
}
// K 2
//
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), MOD)
* modpow(3, modpow(2, K/2, MOD-2) * powOf3 % (MOD-2), MOD);
ans %= MOD;
writeln(ans);
}
long modpow (long a, long x, const long MOD) {
assert(0 <= a);
assert(0 <= x);
// base case
if (x == 0) {
return 1L;
}
if (x == 1) {
return a % MOD;
}
// recursive case
if (x % 2 == 0) {
auto res = modpow(a, x/2, MOD);
return res*res % MOD;
} else {
return modpow(a, x-1, MOD);
}
}
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 input
assert(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;
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0