English · Original
Chinese · Translation
Formal · Original
You are given several queries. Each query consists of three integers $p$, $q$ and $b$. You need to answer whether the result of $p/q$ in notation with base $b$ is a finite fraction.
A fraction in notation with base $b$ is finite if it contains finite number of numerals after the decimal point. It is also possible that a fraction has zero numerals after the decimal point.
## Input
The first line contains a single integer $n$ ($1 \le n \le 10^5$) — the number of queries.
Next $n$ lines contain queries, one per line. Each line contains three integers $p$, $q$, and $b$ ($0 \le p \le 10^{18}$, $1 \le q \le 10^{18}$, $2 \le b \le 10^{18}$). All numbers are given in notation with base $10$.
## Output
For each question, in a separate line, print _Finite_ if the fraction is finite and _Infinite_ otherwise.
[samples]
## Note
$\frac{6}{12} = \frac{1}{2} = 0,5_{10}$
$\frac{4}{3} = 1,(3)_{10}$
$\frac{9}{36} = \frac{1}{4} = 0,01_2$
$\frac{4}{12} = \frac{1}{3} = 0,1_3$
[{"iden":"statement","content":"你被给予若干查询。每个查询由三个整数 $p$、$q$ 和 $b$ 组成。你需要判断 $p \\/ q$ 在以 $b$ 为基数的表示中是否为有限小数。\n\n在以 $b$ 为基数的表示中，一个分数是有限的，当且仅当其小数点后包含有限个数字。也可能小数点后没有数字（即为整数）。\n\n第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 10^5$) —— 查询的数量。\n\n接下来 $n$ 行，每行包含一个查询，包含三个整数 $p$、$q$ 和 $b$ ($0 lt.eq p lt.eq 10^(18)$，$1 lt.eq q lt.eq 10^(18)$，$2 lt.eq b lt.eq 10^(18)$)。所有数字均以十进制表示。\n\n对于每个查询，在单独一行中，若分数为有限小数则输出 _Finite_，否则输出 _Infinite_。\n\n$frac(6, 12) = frac(1, 2) = 0, 5_(10)$\n\n$frac(4, 3) = 1, (3)_(10)$\n\n$frac(9, 36) = frac(1, 4) = 0, 01_2$\n\n$frac(4, 12) = frac(1, 3) = 0, 1_3$ \n\n"},{"iden":"input","content":"第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 10^5$) —— 查询的数量。接下来 $n$ 行，每行包含一个查询，包含三个整数 $p$、$q$ 和 $b$ ($0 lt.eq p lt.eq 10^(18)$，$1 lt.eq q lt.eq 10^(18)$，$2 lt.eq b lt.eq 10^(18)$)。所有数字均以十进制表示。"},{"iden":"output","content":"对于每个查询，在单独一行中，若分数为有限小数则输出 _Finite_，否则输出 _Infinite_。"},{"iden":"examples","content":"输入26 12 104 3 10输出FiniteInfinite输入41 1 29 36 24 12 33 5 4输出FiniteFiniteFiniteInfinite"},{"iden":"note","content":"$frac(6, 12) = frac(1, 2) = 0, 5_(10)$\n$frac(4, 3) = 1, (3)_(10)$\n$frac(9, 36) = frac(1, 4) = 0, 01_2$\n$frac(4, 12) = frac(1, 3) = 0, 1_3$ "}]}
**Definitions**
Let $ n \in \mathbb{Z} $ be the number of queries.
Let $ Q = \{(p_k, q_k, b_k) \mid k \in \{1, \dots, n\}\} $ be the set of queries, where for each $ k $:
- $ p_k, q_k, b_k \in \mathbb{Z} $, with $ 0 \leq p_k < 10^{18} $, $ 1 \leq q_k < 10^{18} $, $ 2 \leq b_k < 10^{18} $.
**Constraints**
1. $ 1 \leq n \leq 10^5 $
2. For each query $ (p_k, q_k, b_k) $:
- $ 0 \leq p_k < 10^{18} $
- $ 1 \leq q_k < 10^{18} $
- $ 2 \leq b_k < 10^{18} $
**Objective**
For each query $ (p_k, q_k, b_k) $, reduce the fraction $ \frac{p_k}{q_k} $ to its lowest terms:
Let $ d_k = \gcd(p_k, q_k) $, and define $ \bar{q}_k = \frac{q_k}{d_k} $.
The fraction $ \frac{p_k}{q_k} $ has a finite representation in base $ b_k $ **if and only if** every prime factor of $ \bar{q}_k $ also divides $ b_k $.
Equivalently, define:
$$
g_k = \gcd(\bar{q}_k, b_k)
$$
Repeatedly divide $ \bar{q}_k $ by $ g_k $ until $ \gcd(\bar{q}_k, b_k) = 1 $.
Then, $ \frac{p_k}{q_k} $ is finite in base $ b_k $ **if and only if** $ \bar{q}_k = 1 $ after this process.
**Output**
For each $ k \in \{1, \dots, n\} $:
- Print **Finite** if $ \bar{q}_k = 1 $ after removing all common factors with $ b_k $.
- Print **Infinite** otherwise.
API Response (JSON)
{
"problem": {
"name": "A. Finite or not?",
"description": {
"content": "You are given several queries. Each query consists of three integers $p$, $q$ and $b$. You need to answer whether the result of $p/q$ in notation with base $b$ is a finite fraction. A fraction in not",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF983A"
},
"statements": [
{
"statement_type": "Markdown",
"content": "You are given several queries. Each query consists of three integers $p$, $q$ and $b$. You need to answer whether the result of $p/q$ in notation with base $b$ is a finite fraction.\n\nA fraction in not...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "[{\"iden\":\"statement\",\"content\":\"你被给予若干查询。每个查询由三个整数 $p$、$q$ 和 $b$ 组成。你需要判断 $p \\\\/ q$ 在以 $b$ 为基数的表示中是否为有限小数。\\n\\n在以 $b$ 为基数的表示中，一个分数是有限的，当且仅当其小数点后包含有限个数字。也可能小数点后没有数字（即为整数）。\\n\\n第一行包含一个整数 $n$ ($1 lt.eq n l...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z} $ be the number of queries. \nLet $ Q = \\{(p_k, q_k, b_k) \\mid k \\in \\{1, \\dots, n\\}\\} $ be the set of queries, where for each $ k $: \n- $ p_k, q_k, b_k \\in \\...",
"is_translate": false,
"language": "Formal"
}
]
}