P6055 [RC-02] GCD

Little A: Number theory problems are really boring. All day long it is just enumerating pairs and triples. So boring. Little B: Yeah, yeah. It is always the same routine. Little A: How about we try enumerating quadruples? Little B: ... And that is how this problem came to be.

Given $N$, compute: $$ \sum_{i=1}^N\sum_{j=1}^N\sum_{p=1}^{\lfloor\frac{N}{j}\rfloor}\sum_{q=1}^{\lfloor\frac{N}{j}\rfloor}[\gcd(i,j)=1][\gcd(p,q)=1] $$ Output the answer modulo $998244353$. $[]$ is a conditional expression. When the statement inside the brackets is true, its value is $1$, otherwise it is $0$.

A single line containing one integer $N$.

Output one integer, the required answer modulo $998244353$.

For all data, it is guaranteed that $1\le N\le 2\times10^9$. The time limit for all test points is $1\text{s}$, and the memory limit is $500\text{MB}$. | Test Point ID | $N$ | | ------------ | ----------------- | | $1$ | $\le 100$ | | $2$ | $\le 400$ | | $3,4,5,6$ | $\le10^6$ | | $7,8$ | $\le 2\times10^7$ | | $9$ | $\le 2\times10^8$ | | $10$ | $\le 2\times10^9$ | This problem could actually have been made into multiple test cases in one input. But the kind problem setter decided to use only one test case, to give you more chances to get partial points. The idea came from @Fee_cle6418. The statement, official solution, and testdata come from @FangZeLi. Translated by ChatGPT 5