AtCoder Beginner Contest 444
翻译中…
Problem Statement
翻译中…
On a two-dimensional coordinate plane, there is a circle with center at point $(\frac{A}{C}, \frac{B}{C})$ and radius $\frac{\sqrt{N}}{C}$. Find the number, modulo $998244353$, of lattice points on the circumference of this circle.
翻译中…
$N$ is given in its prime factorization form as $N=\prod_{i=1}^{M} P_i^{E_i}$.
翻译中…
Constraints
翻译中…
$N \geq 1$$2 \leq P_i \leq 100$$P_i$are distinct primes.$1 \leq E_i \leq 10^{18}$$1 \leq C \leq 50$$0 \leq A,B \lt C$- All input values are integers.
翻译中…
Input
翻译中…
The input is given from Standard Input in the following format:
翻译中…
A B C M
P_1 E_1
P_2 E_2
\vdots
P_M E_M翻译中…
Output
翻译中…
Output the answer.
翻译中…
样例
Input #1
1 1 2 2
2 1
5 2
Output #1
12
As shown in the figure below, there are $12$ lattice points on the circumference.
Input #2
1 5 14 4
2 1
5 1
13 1
17 1
Output #2
4
As shown in the figure below, there are $4$ lattice points on the circumference.
Input #3
1 1 6 3
2 1
5 2
13 1
Output #3
6
As shown in the figure below, there are $6$ lattice points on the circumference.
Input #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
Output #4
7885876
Find the number modulo $998244353$.
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。