← 返回题目列表

AtCoder · arc221_a

A. 两个算术级数

中文机器翻译题面 查看原题

分数: 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.