分数: 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
对于第一个测试用例,答案是 \gcd(4,6)+\gcd(5,10)+\gcd(6,14)+\gcd(7,18)=2+5+2+1=10.