No.2902 ZERO!!
タグ : / 解いたユーザー数 53
作問者 : 👑
cleantted
👑 
amentorimaru
👑 
Nachia
Problem Statement
You are given an integer $N$ greater than or equal to $2$.
For an integer $b$ greater than or equal to $2$, the positive integer $p_b$ and the non-negative integer $e_b$ such that $N!=p_b\times b^{e_b}$ (where $p_b$ is not divisible by $b$) are uniquely determined.
Find $\sum_{b=2}^{N!} e_b$ modulo $998244353$.
Input
$N$
- All inputs are integers.
- $2\leq N\leq 10^6$
Output
Print $\sum_{b=2}^{N!} e_b$ modulo $998244353$, followed by a newline.
Sample
Sample 1
Input
3
Output
3
We have $3!=6$.
For $b=2$, since $6=3\times 2^1$, we get $p_2=3,\ e_2=1$. $3$ is not divisible by $2$.
For $b=3$, since $6=2\times 3^1$, we get $p_3=2,\ e_3=1$. $2$ is not divisible by $3$.
For $b=4$, since $6=6\times 4^0$, we get $p_4=6,\ e_4=0$. $6$ is not divisible by $4$.
For $b=5$, since $6=6\times 5^0$, we get $p_5=6,\ e_5=0$. $6$ is not divisible by $5$.
For $b=6$, since $6=1\times 6^1$, we get $p_6=1,\ e_6=1$. $1$ is not divisible by $6$.
Therefore, the answer is $\sum_{b=2}^{N!} e_b=\sum_{b=2}^{6} e_b=1+1+0+0+1=3$.
Sample 2
Input
7
Output
66
Sample 3
Input
1000000
Output
529018025
Print the remainder when divided by $998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。