A. 两个等差数列

AtCoder Regular Contest++ 221

两个等差数列

Two Arithmetic Progressions

AtCoder

⌀ 1686

原题

←B →

两个等差数列AI (CI翻译)

Problem Statement

题目描述

AI (CI翻译)

You are given positive integers $N,A,B,C,D$ .

给定正整数 $N,A,B,C,D$ 。AI (CI翻译)

Find $\displaystyle \sum_{i=1}^N \gcd (Ai+B,Ci+D)$ , modulo $998244353$ . Here, $\gcd(x,y)$ denotes the greatest common divisor of $x$ and $y$ .

求 $\diplaystyle \sum_{i=1}^N \gcd (Ai+B,Ci+D)$ 对 $998244353$ 取模的结果。其中， $\gcd(x,y)$ 表示 $x$ 和 $y$ 的最大公约数。AI (CI翻译)

You are given $T$ test cases; solve each of them.

给定 $T$ 个测试用例，请分别求出每个测试用例的答案。AI (CI翻译)

Constraints

约束条件

AI (CI翻译)

$1\leq T\leq 200$
$1\leq N\leq 10^9$
$1\leq A,B,C,D\leq 10^4$
All input values are integers.

$1\leq T\leq 200$
$1\leq N\leq 10^9$
$1\leq A,B,C,D\leq 10^4$
所有输入值均为整数。

AI (CI翻译)

Input

输入格式

AI (CI翻译)

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

输入从标准输入按以下格式给出：AI (CI翻译)

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

AI (CI翻译)

Each test case is given in the following format:

每个测试用例的格式如下：AI (CI翻译)

N A B C D

N A B C D

AI (CI翻译)

Output

输出格式

AI (CI翻译)

Output the answers for the test cases in order, separated by newlines.

按顺序输出各个测试用例的答案，每个答案占一行。AI (CI翻译)

样例

Input #1

3
4 1 3 4 2
100000000 1 1 1 2
100000000 1 1 1 1

Output #1

10
100000000
822404071

For the first test case, the answer is $\gcd(4,6)+\gcd(5,10)+\gcd(6,14)+\gcd(7,18)=2+5+2+1=10$.

题目信息

题号

arc221_a

所属比赛

AtCoder Regular Contest++ 221

时间限制

2 s

内存限制

1024 MB

题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。