E - Count A%B=C
解説
/ 
/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 475 点
問題文
整数の組 (a, b, c) であって以下の条件を満たすものの個数を 998244353 で割ったあまりを求めてください。
- 1 \leq a,b,c \leq N
- a,b,c は相異なる。
- a を b で割ったあまりは c に等しい。
制約
- 3 \leq N \leq 10^{12}
- N は整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを 1 行で出力せよ。
入力例 1
7
出力例 1
12
条件を満たす整数の組 (a,b,c) は以下の 12 通り存在します。
- (3,2,1)
- (4,3,1)
- (5,2,1)
- (5,3,2)
- (5,4,1)
- (6,4,2)
- (6,5,1)
- (7,2,1)
- (7,3,1)
- (7,4,3)
- (7,5,2)
- (7,6,1)
入力例 2
441
出力例 2
94700
入力例 3
411111111114
出力例 3
462474062
Score : 475 points
Problem Statement
Find the number, modulo 998244353, of integer tuples (a, b, c) that satisfy the following conditions.
- 1 \leq a,b,c \leq N
- a,b,c are pairwise distinct.
- The remainder when a is divided by b is equal to c.
Constraints
- 3 \leq N \leq 10^{12}
- N is an integer.
Input
The input is given from Standard Input in the following format:
N
Output
Output the answer in one line.
Sample Input 1
7
Sample Output 1
12
There are 12 integer tuples (a,b,c) that satisfy the conditions:
- (3,2,1)
- (4,3,1)
- (5,2,1)
- (5,3,2)
- (5,4,1)
- (6,4,2)
- (6,5,1)
- (7,2,1)
- (7,3,1)
- (7,4,3)
- (7,5,2)
- (7,6,1)
Sample Input 2
441
Sample Output 2
94700
Sample Input 3
411111111114
Sample Output 3
462474062