/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 900 点
問題文
正整数 N と、0 \leq n \lt m \leq N を満たす整数 n,m が与えられます。
以下の擬似コードで定義される関数 f は、非負整数 i と j の最大公約数をユークリッドの互除法で求める関数です。
function f(i, j)
if i = 0 then
return j
end if
return f(j mod i, i)
end function
ただし、j mod i は j を i で割った余りを表します。
0 \leq i\leq j \leq N を満たすすべての整数の組 (i,j) について f(i,j) を 1 回ずつ実行したとき、f(n,m) が呼び出される回数を 998244353 で割った余りを求めてください。
より厳密には、以下の擬似コードが出力する整数を 998244353 で割った余りを求めてください。
answer ← 0
function f(i, j)
if (i, j) = (n, m) then
answer ← answer + 1
end if
if i = 0 then
return j
end if
return f(j mod i, i)
end function
for i = 0 to N do
for j = i to N do
f(i, j)
end for
end for
output answer
1 つの入力につき、T 個のテストケースを解いてください。
制約
- 1 \leq T \leq 10^5
- 1 \leq N \leq 10^{18}
- 0 \leq n \lt m \leq N
- すべてのテストケースにおける \left\lfloor\frac{N}{m}\right\rfloor の総和は 10^6 以下
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
各テストケース \mathrm{case}_t は以下の形式で与えられる。
N n m
出力
答えを合計 T 行で出力せよ。 t 行目には、t 番目のテストケースの答えを出力せよ。
入力例 1
5 5 1 2 233 100 199 1000000 233 234 57306 0 1 57307 0 1
出力例 1
4 1 5563182 998216169 25736
1 つ目のテストケースでは、(N,n,m)=(5,1,2) です。
f(2,3) を実行したとき、
f(2,3) \rightarrow f(1,2) \rightarrow f(0,1)
の順に呼び出されるため、f(1,2) が呼び出される回数は 1 回です。
(i,j)=(1,2),(2,3),(2,5),(3,5) のそれぞれについて f(i,j) を実行すると f(1,2) は 1 回ずつ呼び出されるため、1 つ目のテストケースの答えは 4 です。
Score : 900 points
Problem Statement
You are given a positive integer N and integers n,m satisfying 0 \leq n \lt m \leq N.
The function f defined by the following pseudocode computes the greatest common divisor of non-negative integers i and j by the Euclidean algorithm.
function f(i, j)
if i = 0 then
return j
end if
return f(j mod i, i)
end function
Here, j mod i denotes the remainder when j is divided by i.
Suppose that f(i,j) is executed once for every pair of integers (i,j) satisfying 0 \leq i\leq j \leq N. Find the number of times f(n,m) is called, modulo 998244353.
More formally, find the integer printed by the following pseudocode, modulo 998244353.
answer ← 0
function f(i, j)
if (i, j) = (n, m) then
answer ← answer + 1
end if
if i = 0 then
return j
end if
return f(j mod i, i)
end function
for i = 0 to N do
for j = i to N do
f(i, j)
end for
end for
output answer
Solve T test cases for each input.
Constraints
- 1 \leq T \leq 10^5
- 1 \leq N \leq 10^{18}
- 0 \leq n \lt m \leq N
- The sum of \left\lfloor\frac{N}{m}\right\rfloor over all test cases is at most 10^6.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
Each test case \mathrm{case}_t is given in the following format:
N n m
Output
Print T lines in total. The t-th line should contain the answer for the t-th test case.
Sample Input 1
5 5 1 2 233 100 199 1000000 233 234 57306 0 1 57307 0 1
Sample Output 1
4 1 5563182 998216169 25736
In the first test case, (N,n,m)=(5,1,2).
When f(2,3) is executed, the calls are made in the order
f(2,3) \rightarrow f(1,2) \rightarrow f(0,1),
so f(1,2) is called once.
When f(i,j) is executed for each of (i,j)=(1,2),(2,3),(2,5),(3,5), f(1,2) is called once in each case, so the answer for the first test case is 4.