AT_arc233_b.Count of Euclid Function Call
省选/NOI-
通过率:0%
时间限制:2.00s
内存限制:1024MB
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are given a positive integer N and integers n,m satisfying 0≤n<m≤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≤i≤j≤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.
给定一个正整数 N,以及满足 0≤n<m≤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≤i≤j≤N 的整数对 (i,j),均执行一次 f(i,j)。求 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
对每组输入,求解 T 个测试用例。
输入格式
The input is given from Standard Input in the following format:
T
case1
case2
⋮
caseT
Each test case caset is given in the following format:
N n m
输入从标准输入中按以下格式给出:
T
case1
case2
⋮
caseT
每个测试用例 caset 的格式如下:
N n m
输出格式
Print T lines in total. The t-th line should contain the answer for the t-th test case.
共输出 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
说明/提示
Sample 1 Explanation:
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)→f(1,2)→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.
Constraints
- 1≤T≤105
- 1≤N≤1018
- 0≤n<m≤N
- The sum of ⌊mN⌋ over all test cases is at most 106.
- All input values are integers.
样例 1 解释:
在第一个测试用例中,(N,n,m)=(5,1,2)。
当执行 f(2,3) 时,函数调用顺序为
f(2,3)→f(1,2)→f(0,1),
因此 f(1,2) 被调用了一次。
当对 (i,j)=(1,2),(2,3),(2,5),(3,5) 中的每一组分别执行 f(i,j) 时,f(1,2) 在每种情况下均被调用一次,因此第一个测试用例的答案为 4。
约束条件
- 1≤T≤105
- 1≤N≤1018
- 0≤n<m≤N
- 所有测试用例中 ⌊mN⌋ 的总和不超过 106。
- 所有输入值均为整数。
输入解题思路,AI测评打分。不知道怎么写?