题目描述
Problem Background
Xiao A: Number theory problems are so boring, always enumerating pairs and triples, it's too monotonous.
Xiao B: Exactly, it's all routine.
Xiao A: How about we try enumerating quadruples?
Xiao B: ...
And thus, this problem was born.
Problem Description
Given \( N \), find:
\[ \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] \]
The answer should be modulo \( 998244353 \).
The \( [] \) is an indicator function. It evaluates to \( 1 \) if the condition inside is true, otherwise \( 0 \).
Input Format
A single line containing an integer \( N \).
Output Format
Output a single integer, which is the result of the expression modulo \( 998244353 \).
Sample Input and Output
Input Sample #1
50
Output Sample #1
104527
Input Sample #2
200
Output Sample #2
6664993
Input Sample #3
500000
Output Sample #3
835964450
Input Sample #4
10000000
Output Sample #4
503290049
Input Sample #5
100000000
Output Sample #5
712748411
Input Sample #6
1000000000
Output Sample #6
845640070
Notes
For all test cases, it is guaranteed that \( 1 \le N \le 2 \times 10^9 \). All test points have a time limit of \( 1 \) second and a memory limit of \( 500 \) MB.
| Test Case Number | \( N \) |
|---|---|
| 1 | \( \le 100 \) |
| 2 | \( \le 400 \) |
| 3, 4, 5, 6 | \( \le 10^6 \) |
| 7, 8 | \( \le 2 \times 10^7 \) |
| 9 | \( \le 2 \times 10^8 \) |
| 10 | \( \le 2 \times 10^9 \) |
This problem could have had multiple data sets per test point, but the kind problem setter decided to give you more partial scores by providing only one data set.
The idea originated from @Fee_cle6418, and the problem statement, solution, and data were created by @FangZeLi.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分