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.
For each query $ k \in \{1, \dots, n\} $, let $ (p_k, q_k, b_k) \in \mathbb{Z}^3 $ be the input triple, where:
- $ 0 \leq p_k \leq 10^{18} $,
- $ 1 \leq q_k \leq 10^{18} $,
- $ 2 \leq b_k \leq 10^{18} $.
Let $ r_k = \frac{p_k}{q_k} $, and define $ \tilde{r}_k = \frac{p_k / \gcd(p_k, q_k)}{q_k / \gcd(p_k, q_k)} = \frac{p_k'}{q_k'} $ as the reduced form of the fraction.
**Constraints**
1. $ 1 \leq n \leq 10^5 $
2. For all $ k \in \{1, \dots, n\} $:
- $ 0 \leq p_k \leq 10^{18} $
- $ 1 \leq q_k \leq 10^{18} $
- $ 2 \leq b_k \leq 10^{18} $
**Objective**
For each query $ k $, determine whether the fractional part of $ \tilde{r}_k = \frac{p_k'}{q_k'} $ has a finite representation in base $ b_k $.
This occurs **if and only if** all prime factors of $ q_k' $ are also prime factors of $ b_k $.
Equivalently:
Let $ d_k = \gcd(p_k, q_k) $, and $ q_k' = \frac{q_k}{d_k} $.
Let $ g_k = \gcd(q_k', b_k) $.
While $ g_k > 1 $, replace $ q_k' $ by $ \frac{q_k'}{g_k} $ and $ g_k $ by $ \gcd(q_k', b_k) $.
Then, $ \frac{p_k}{q_k} $ has a finite representation in base $ b_k $ **if and only if** $ q_k' = 1 $ after this process.
**Output**
For each $ k $, output:
- “Finite” if $ q_k' = 1 $ after removing all common factors with $ b_k $,
- “Infinite” otherwise.
API Response (JSON)
{
"problem": {
"name": "C. 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": "CF984C"
},
"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 lt.eq 10...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z} $ be the number of queries. \nFor each query $ k \\in \\{1, \\dots, n\\} $, let $ (p_k, q_k, b_k) \\in \\mathbb{Z}^3 $ be the input triple, where: \n- $ 0 \\leq p_k \\...",
"is_translate": false,
"language": "Formal"
}
]
}