/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 600 点
問題文
正整数 N,A,B,C,D が与えられます．
\displaystyle \sum_{i=1}^N \gcd (Ai+B,Ci+D) を 998244353 で割った余りを求めてください．ただし，\gcd(x,y) で x と y の最大公約数を表します．
T 個のテストケースが与えられるので，それぞれについて答えを求めてください．
制約
- 1\leq T\leq 200
- 1\leq N\leq 10^9
- 1\leq A,B,C,D\leq 10^4
- 入力される数値は全て整数
入力
入力は以下の形式で標準入力から与えられる．
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
各テストケースは以下の形式で与えられる．
N A B C D
出力
各テストケースに対する答えを順に改行区切りで出力せよ．
入力例 1
3 4 1 3 4 2 100000000 1 1 1 2 100000000 1 1 1 1
出力例 1
10 100000000 822404071
1 番目のテストケースについて，答えは \gcd(4,6)+\gcd(5,10)+\gcd(6,14)+\gcd(7,18)=2+5+2+1=10 です．
Score : 600 points
Problem Statement
You are given positive integers N,A,B,C,D.
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.
You are given T test cases; solve each of them.
Constraints
- 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.
Input
The input is given from Standard Input in the following format:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
Each test case is given in the following format:
N A B C D
Output
Output the answers for the test cases in order, separated by newlines.
Sample Input 1
3 4 1 3 4 2 100000000 1 1 1 2 100000000 1 1 1 1
Sample 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.