No.3607 Sum of Powers of GCDs
loop0919
ぽえ問題文
正整数 $N, M, K$ が与えられます。
$1$ 以上 $M$ 以下の整数からなる長さ $N$ の数列 $A = (a_1, a_2, \cdots, a_N)$ について考えます。
そのようなものは $M^N$ 個存在しますが、これらすべてについて $\gcd(a_1, a_2, \cdots, a_N)$ の $K$ 乗を求め、それらの総和を求めてください。
ただし、答えは非常に大きくなる可能性があるため、答えを $998244353$ で割った余りを出力してください。
$T$ 個のテストケースが与えられるので、それぞれについて答えてください。
$\gcd$ とは（クリックで開く）
$\gcd (a_1, a_2, \cdots, a_N)$ とは、 $a_1, a_2, \cdots, a_N$ の最大公約数を表します。
制約
- 入力される値はすべて整数
- $1 \leq T \leq 2000$
- $1 \leq N, M \leq 10^6$
- $1 \leq K \leq 10$
入力
入力は以下の形式で標準入力から与えられる。
$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$
各テストケースは以下の形式で与えられる。
$N$ $M$ $K$
出力
各テストケースについての答えを $998244353$ で割った余りを順に改行区切りで出力せよ。
サンプル
サンプル1
入力
3 2 3 4 1 100 1 1000000 1000000 10
出力
104 5050 230008598
$1$ 番目のテストケースについて考えます。
$1$ 以上 $3$ 以下の整数からなる長さ $2$ の数列すべてについて、それぞれ最大公約数を考えます。
- $\gcd(1, 1) = 1$
- $\gcd(1, 2) = 1$
- $\gcd(1, 3) = 1$
- $\gcd(2, 1) = 1$
- $\gcd(2, 2) = 2$
- $\gcd(2, 3) = 1$
- $\gcd(3, 1) = 1$
- $\gcd(3, 2) = 1$
- $\gcd(3, 3) = 3$
これらをそれぞれ $4$ 乗し、それらの総和を取ると $104$ になります。
$3$ 番目のテストケースについて、 $998244353$ で割った余りを出力することを忘れないよう注意してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。