問題一覧 > 通常問題

No.3186 Big Order

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 22
作問者 : 蜜蜂 / テスター : Mitarushi
2 ProblemId : 12327 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-06-21 18:44:00

問題文

正整数 $A, B, C$ が与えられるので，$A^B$ が $C$ で割り切れる回数を $998244353$ で割ったあまりを求めてください．
ここで，$C$ は $2$ 以上であることが保証されます．

$T$ 個のテストケースが与えられるのでそれぞれについて答えを求めてください．

入力

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$
ここで，$\mathrm{case}_i$ は $i$ 番目のテストケースを意味し，各テストケースは以下の形式で与えられます．
$A\ \ B\ \ C$

  • $1 \leq T \leq 100$
  • $1 \leq A, B \leq 10^{40}$
  • $2 \leq C \leq 10^{40}$
  • 入力はすべて整数

出力

各テストケースについて，$A^B$ が $C$ で割り切れる回数を $998244353$ で割ったあまりを出力し改行してください．

サンプル

サンプル1
入力
3
2 3 4
1 2 3
2 1000000000 2
出力
1
0
1755647

  • $1$ 番目のテストケースについて，$A^B = 8$ が $4$ で割り切れる回数は $1$ 回です．
  • $2$ 番目のテストケースについて，$A^B = 1$ が $3$ で割り切れる回数は $0$ 回です．
  • $3$ 番目のテストケースについて，$998244353$ で割ったあまりを出力することに気をつけてください．

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。