P6055 [RC-02] GCD

小 A：数论题真是无聊呢，一天到晚枚举二元组、三元组，太无聊了。 小 B：对呀对呀，都是套路。 小 A：要不我们试试枚举四元组？ 小 B：...... 于是就有了这道题。

给出 $N$，求： $$ \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] $$ 答案模 $998244353$。 $[]$ 是条件表达式。当括号里面的式子成立时值为 $1$，否则为 $0$。

无

无

对于所有数据，保证 $1\le N\le 2\times10^9$，所有测试点的时限均为 $1\text{s}$，空间限制均为 $500\text{MB}$。 | 测试点编号 | $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$ | 这题其实可以搞一个测试点多组数据，但良心的出题人为了多给你们一点部分分，就决定只来一组数据。 idea 源自 @Fee_cle6418，题目的题面，标算，数据源自 @FangZeLi。