{"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 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.\n\n## Input\n\nThe first line contains a single integer $n$ ($1 \\le n \\le 10^5$) — the number of queries.\n\nNext $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$.\n\n## Output\n\nFor each question, in a separate line, print _Finite_ if the fraction is finite and _Infinite_ otherwise.\n\n[samples]\n\n## Note\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$","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^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$ \"}]}","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 \\mathbb{Z} $, with $ 0 \\leq p_k < 10^{18} $, $ 1 \\leq q_k < 10^{18} $, $ 2 \\leq b_k < 10^{18} $.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^5 $  \n2. For each query $ (p_k, q_k, b_k) $:  \n   - $ 0 \\leq p_k < 10^{18} $  \n   - $ 1 \\leq q_k < 10^{18} $  \n   - $ 2 \\leq b_k < 10^{18} $  \n\n**Objective**  \nFor each query $ (p_k, q_k, b_k) $, reduce the fraction $ \\frac{p_k}{q_k} $ to its lowest terms:  \nLet $ d_k = \\gcd(p_k, q_k) $, and define $ \\bar{q}_k = \\frac{q_k}{d_k} $.  \n\nThe 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 $.  \n\nEquivalently, define:  \n$$\ng_k = \\gcd(\\bar{q}_k, b_k)\n$$  \nRepeatedly divide $ \\bar{q}_k $ by $ g_k $ until $ \\gcd(\\bar{q}_k, b_k) = 1 $.  \nThen, $ \\frac{p_k}{q_k} $ is finite in base $ b_k $ **if and only if** $ \\bar{q}_k = 1 $ after this process.  \n\n**Output**  \nFor each $ k \\in \\{1, \\dots, n\\} $:  \n- Print **Finite** if $ \\bar{q}_k = 1 $ after removing all common factors with $ b_k $.  \n- Print **Infinite** otherwise.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF983A","tags":["implementation","math"],"sample_group":[["2\n6 12 10\n4 3 10","Finite\nInfinite"],["4\n1 1 2\n9 36 2\n4 12 3\n3 5 4","Finite\nFinite\nFinite\nInfinite"]],"created_at":"2026-03-03 11:00:39"}}