AT_abc444_g.[ABC444G] Kyoen

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

在二维坐标平面上，有一个圆，其圆心在点 $(\frac{A}{C}, \frac{B}{C})$ ，半径为 $\frac{\sqrt{N}}{C}$ 。请你求出该圆的周长上有多少个整点，并对 $998244353$ 取模。

$N$ 已经按照其质因数分解的形式给出，即 $N = \prod_{i=1}^{M} P_i^{E_i}$ 。

输入格式

输入从标准输入中获得，格式如下：

$A\ B\ C\ M\ P_1\ E_1\ P_2\ E_2\ \cdots\ P_M\ E_M$

输出格式

输出答案。

输入输出样例

输入#1
```
1 1 2 2
2 1
5 2
```
输出#1
```
12
```
输入#2
```
1 5 14 4
2 1
5 1
13 1
17 1
```
输出#2
```
4
```
输入#3
```
1 1 6 3
2 1
5 2
13 1
```
输出#3
```
6
```

输入#4

0 0 1 10
97 1000000000000000000
89 1000000000000000000
73 1000000000000000000
61 1000000000000000000
59 1000000000000000000
47 1000000000000000000
31 1000000000000000000
23 1000000000000000000
11 1000000000000000000
5 1000000000000000000

输出#4

说明/提示

样例解释 1

如下图所示，该圆周长上有 $12$ 个整点。

样例解释 2

如下图所示，该圆周长上有 $4$ 个整点。

样例解释 3

如下图所示，该圆周长上有 $6$ 个整点。

样例解释 4

请将结果对 $998244353$ 取模。

数据范围

$N \geq 1$
$2 \leq P_i \leq 100$
$P_i$ 均为互不相同的质数。
$1 \leq E_i \leq 10^{18}$
$1 \leq C \leq 50$
$0 \leq A,B < C$
所有输入值均为整数。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页