题目链接:

http://codeforces.com/contest/984/problem/C


题目:

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≤n≤10^5)$ — the number of queries.

Next nn lines contain queries, one per line. Each line contains three integers $p$, $q$, and$b (0≤p≤10^{18}, 1≤q≤10^{18}, 2≤b≤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.


题意:

  n组样例,对于每组样例,给你三个数p q b,问你$\frac{p}{q}$在$b$进制下是不是一个有限小数,是的话输出Finite,否则输出Infinite


思路:

  首先对于$\frac{p}{q}$可以先对分子分母约分一下,然后只关心$\frac{1}{q}$是否可以在$b$进制下被有限表示即可,因为他们俩之间只相差一个系数$p$,也就是说如果$\frac{1}{q}$可以被有限表示,那么$\frac{p}{q}$也一定可以被有限表示。

  考虑$\frac{1}{q}$,一定是一个小于等于$1$的数,考虑将小数转化为$b$进制的过程,每次将小数乘以$b$然后取整数部分,直到这个小数变成了$0$,也就是说如果某个小数$\frac{1}{q}$在$b$进制下可以被有限表示,那么一定存在一个$i$,使得$b^i = 0\ (mod\ q)$成立,于是我们判断这个$i$是否存在即可。

  判断的方法刚开始一直想不出来,莽了一发BSGS果断TLE了(我还是太弱了),听了小伙伴的思路才过的。

  考虑$b^i$,其不同因子的个数恒等于$b$的不同因子的个数,于是判断$b^i\ mod\ q$是否可以等于$0$就等价于判断$b$是否拥有所有$q$的因子。


实现:

#include <bits/stdc++.h>
typedef long long ll;
ll gcd(ll p, ll q) { return q ? gcd(q, p % q) : p; }
ll p, q, b, tmp, i, n;

int main() {
    for (i = 0, scanf("%lld", &n); i < n; i++){
        scanf("%lld%lld%lld", &p, &q, &b);
        q = q / gcd(p, q);
        while ((tmp = gcd(q, b)) != 1) while (q % tmp == 0) q /= tmp;
        puts(q == 1 ? "Finite" : "Infinite");
    }
    return 0;
}
最后修改:2018 年 06 月 09 日 11 : 48 PM
谢谢老板!