← 返回题目列表

AtCoder · arc216_d

D. 算术级数乘积的 GCD

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

分数: 1000 点

问题陈述

给你正整数 N, B, C, D.

对于非负整数 k,定义整数 a_k 作为算术序列的所有项与第一项的乘积 Bk + C,共同差异 D,和 N 条款;也就是说, a_k = (Bk+C)(Bk+C+D)(Bk+C+2D)\dots(Bk+C+(N-1)D).

求最大公约数,模 998244353,属于 a_0, a_1, a_2, \ldots, a_N.

你被给予 T 测试用例;解决它们中的每一个。

约束

  • 1 \leq T \leq 10^5
  • 1 \leq N, B, C, D \leq 10^6
  • 所有输入值均为整数。

输入

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

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

每个测试用例均按以下格式给出:

N B C D

输出

输出 T 行。的 i- 第行应包含以下问题的答案 \mathrm{case}_i.


示例输入 1

3
3 1 1 1
4 2 2 6
2026 3 22 216

示例输出 1

6
128
114347907

对于第一个测试用例, (a_0, a_1, a_2, a_3) = (1 \times 2 \times 3, 2 \times 3 \times 4, 3 \times 4 \times 5, 4 \times 5 \times 6) = (6, 24, 60, 120),它们的最大公约数是 6.