No.1760 Setwise Coprime
タグ : / 解いたユーザー数 23
作問者 :
PCTprobability
/ テスター :
NyaanNyaan
tokusakurai
Problem Statement
Find the number, modulo $998244353$, of pairs of sets $A,B$ consisting of positive integers between $1$ and $N$, inclusive, that satisfy all of the following conditions.
- Neither $A$ nor $B$ is empty.
- $A$ and $B$ have no common elements.
- The greatest common divisor of all elements of $A$ and the greatest common divisor of all elements of $B$ are both $1$.
Constraints
- All input values are integers.
- $2 \le N \le 2 \times 10^5$
Input
$N$
Output
Output the answer in $1$ line.
Sample
Sample 1
Input
4
Output
10
For example, $A=\{1,4\},B=\{2,3\}$ satisfies the conditions.
$A=\{\},B=\{2,3,4\}$ does not satisfy the conditions because $A$ is empty.
$A=\{2,3\},B=\{3,4\}$ does not satisfy the conditions because $3$ is a common element of $A$ and $B$.
$A=\{2,4\},B=\{1\}$ does not satisfy the conditions because the greatest common divisor of all elements of $A$ is $2$.
Sample 2
Input
10
Output
37834
Sample 3
Input
2021
Output
199287659
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。