D. 等差数列乘积的最大公约数

AtCoder Regular Contest++ 216

等差数列乘积的最大公约数

GCD of Product of Arithmetic Progression

AtCoder

⌀ 3079

原题

← CE →

等差数列乘积的最大公约数AI (CI翻译)

Problem Statement

题目描述

AI (CI翻译)

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

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

For a non-negative integer $k$ , define the integer $a_k$ as the product of all terms of an arithmetic sequence with first term $Bk + C$ , common difference $D$ , and $N$ terms; that is, $a_k = (Bk+C)(Bk+C+D)(Bk+C+2D)\dots(Bk+C+(N-1)D)$ .

对于非负整数 $k$ ，定义整数 $a_k$ 为首项为 $Bk + C$ 、公差为 $D$ 、项数为 $N$ 的等差数列中所有项的乘积，即 $a_k = (Bk+C)(Bk+C+D)(Bk+C+2D)\dots(Bk+C+(N-1)D)$ 。AI (CI翻译)

Find the greatest common divisor, modulo $998244353$ , of $a_0, a_1, a_2, \ldots, a_N$ .

求 $a_0, a_1, a_2, \ldots, a_N$ 的最大公约数对 $998244353$ 取模后的结果。AI (CI翻译)

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

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

Constraints

约束条件

AI (CI翻译)

$1 \leq T \leq 10^5$
$1 \leq N, B, C, D \leq 10^6$
All input values are integers.

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

AI (CI翻译)

Input

输入格式

AI (CI翻译)

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

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

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

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

AI (CI翻译)

Each test case is given in the following format:

每组测试用例按以下格式给出：AI (CI翻译)

N B C D

N B C D

AI (CI翻译)

Output

输出格式

AI (CI翻译)

Output $T$ lines. The $i$ -th line should contain the answer to $\mathrm{case}_i$ .

输出 $T$ 行。第 $i$ 行应包含 $\mathrm{case}_i$ 的答案。AI (CI翻译)

样例

Input #1

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

Output #1

6
128
114347907

For the first test case, $(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)$, and their greatest common divisor is $6$.

题目信息

题号

arc216_d

所属比赛

AtCoder Regular Contest++ 216

时间限制

2 s

内存限制

1024 MB

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