AT_arc233_b.Count of Euclid Function Call

省选/NOI-

通过率:0%

时间限制:2.00s

内存限制:1024MB

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

You are given a positive integer NN and integers n,mn,m satisfying 0≤n<m≤N0 \leq n \lt m \leq N.

The function ff defined by the following pseudocode computes the greatest common divisor of non-negative integers ii and jj 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 jj is divided by ii.
Suppose that f(i,j)f(i,j) is executed once for every pair of integers (i,j)(i,j) satisfying 0≤i≤j≤N0 \leq i\leq j \leq N. Find the number of times f(n,m)f(n,m) is called, modulo 998244353998244353.

More formally, find the integer printed by the following pseudocode, modulo 998244353998244353.

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 TT test cases for each input.

给定一个正整数 NN,以及满足 0≤n<m≤N0 \leq n \lt m \leq N 的整数 n,mn,m。

以下伪代码定义的函数 ff 通过欧几里得算法计算两个非负整数 ii 和 jj 的最大公约数:

function f(i, j)
    if i = 0 then
        return j
    end if
    return f(j mod i, i)
end function

其中,j mod i 表示 jj 除以 ii 所得的余数。
假设对所有满足 0≤i≤j≤N0 \leq i \leq j \leq N 的整数对 (i,j)(i,j),均执行一次 f(i,j)f(i,j)。求 f(n,m)f(n,m) 被调用的次数,对 998244353998244353 取模。

更形式化地,求以下伪代码所输出的整数对 998244353998244353 取模的结果:

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

对每组输入,求解 TT 个测试用例。

输入格式

The input is given from Standard Input in the following format:

TT
case1\mathrm{case}_1
case2\mathrm{case}_2
⋮\vdots
caseT\mathrm{case}_T

Each test case caset\mathrm{case}_t is given in the following format:

NN nn mm

输入从标准输入中按以下格式给出:

TT
case1\mathrm{case}_1
case2\mathrm{case}_2
⋮\vdots
caseT\mathrm{case}_T

每个测试用例 caset\mathrm{case}_t 的格式如下:

NN nn mm

输出格式

Print TT lines in total. The tt-th line should contain the answer for the tt-th test case.

共输出 TT 行。第 tt 行应包含第 tt 个测试用例的答案。

输入输出样例

  • 输入#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)(N,n,m)=(5,1,2).
When f(2,3)f(2,3) is executed, the calls are made in the order
f(2,3)→f(1,2)→f(0,1)f(2,3) \rightarrow f(1,2) \rightarrow f(0,1),
so f(1,2)f(1,2) is called once.
When f(i,j)f(i,j) is executed for each of (i,j)=(1,2),(2,3),(2,5),(3,5)(i,j)=(1,2),(2,3),(2,5),(3,5), f(1,2)f(1,2) is called once in each case, so the answer for the first test case is 44.

Constraints

  • 1≤T≤1051 \leq T \leq 10^5
  • 1≤N≤10181 \leq N \leq 10^{18}
  • 0≤n<m≤N0 \leq n \lt m \leq N
  • The sum of ⌊Nm⌋\left\lfloor\frac{N}{m}\right\rfloor over all test cases is at most 10610^6.
  • All input values are integers.

样例 1 解释:
在第一个测试用例中,(N,n,m)=(5,1,2)(N,n,m)=(5,1,2)。
当执行 f(2,3)f(2,3) 时,函数调用顺序为
f(2,3)→f(1,2)→f(0,1)f(2,3) \rightarrow f(1,2) \rightarrow f(0,1),
因此 f(1,2)f(1,2) 被调用了一次。
当对 (i,j)=(1,2),(2,3),(2,5),(3,5)(i,j)=(1,2),(2,3),(2,5),(3,5) 中的每一组分别执行 f(i,j)f(i,j) 时,f(1,2)f(1,2) 在每种情况下均被调用一次,因此第一个测试用例的答案为 44。

约束条件

  • 1≤T≤1051 \leq T \leq 10^5
  • 1≤N≤10181 \leq N \leq 10^{18}
  • 0≤n<m≤N0 \leq n \lt m \leq N
  • 所有测试用例中 ⌊Nm⌋\left\lfloor\frac{N}{m}\right\rfloor 的总和不超过 10610^6。
  • 所有输入值均为整数。

输入解题思路,AI测评打分。不知道怎么写?

首页