No.2902 ZERO!!
タグ : / 解いたユーザー数 38
作問者 : 👑
cleantted
👑 
amentorimaru
👑 
Nachia
問題文
$2$ 以上の整数 $N$ が与えられます。
$2$ 以上の整数 $b$ をとったとき、 $N!=p_b\times b^{e_b}$ （ただし $p_b$ は $b$ で割り切れない）となる正の整数 $p_b$ と非負整数 $e_b$ が一意に定まります。
$\sum_{b=2}^{N!} e_b$ を $998244353$ で割った余りを求めてください。
入力
$N$
- 入力は全て整数
- $2\leq N\leq 10^6$
出力
$\sum_{b=2}^{N!} e_b$ を $998244353$ で割った余りを出力し、最後に改行してください。
サンプル
サンプル1
入力
3
出力
3
$3!=6$ です。
$b=2$ の場合、 $6=3\times 2^1$ より $p_2=3,\ e_2=1$ となります。 $3$ は $2$ で割り切れません。
$b=3$ の場合、 $6=2\times 3^1$ より $p_3=2,\ e_3=1$ となります。 $2$ は $3$ で割り切れません。
$b=4$ の場合、 $6=6\times 4^0$ より $p_4=6,\ e_4=0$ となります。 $6$ は $4$ で割り切れません。
$b=5$ の場合、 $6=6\times 5^0$ より $p_5=6,\ e_5=0$ となります。 $6$ は $5$ で割り切れません。
$b=6$ の場合、 $6=1\times 6^1$ より $p_6=1,\ e_6=1$ となります。 $1$ は $6$ で割り切れません。
よって、 $\sum_{b=2}^{N!} e_b=\sum_{b=2}^{6} e_b=1+1+0+0+1=3$ が答えとなります。
サンプル2
入力
7
出力
66
サンプル3
入力
1000000
出力
529018025
$998244353$ で割った余りを出力してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。