[RC-02] GCD

ID: 5005

远端评测题

1000ms

500MiB

尝试: 0

已通过: 0

难度: 6

上传者:

root

题目背景

小 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$ 。

输入格式

仅一行一个整数，为 $N$ 。

输出格式

输出一个整数，为所求答案模上 $998244353$ 的值。

输入数据 1

输出数据 1

输入数据 2

输出数据 2

输入数据 3

输出数据 3

835964450

输入数据 4

10000000

输出数据 4

503290049

输入数据 5

100000000

输出数据 5

712748411

输入数据 6

1000000000

输出数据 6

845640070

提示

对于所有数据，保证 $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。

#P6055. [RC-02] GCD