ACM模版

描述

题解

首先求 p、q p 、 q 的最大公约数，为了在十进制下约分，此时我们先考虑十进制的情况什么条件才能有限，最简分数 ab a b 能化为有限小数的充要条件是分母 b b 不含有 2 和 5 5 以外的质因数，那么我们可以尝试猜一下， p q 在 b b 进制下想要有限的充要条件是 q 不含 b b 拆解后的质因数以外的质因数。所以此时我们无需考虑 p ，只用不断去除 q q 中的 b 的质因子，如果可以最后把 q q 拆解成 1 那么就是有限，否则无限。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;

int n;

ll gcd(ll x, ll y)
{
    if (!x || !y)
    {
        return x > y ? x : y;
    }

    for (ll t; static_cast<void>(t = x % y), t; x = y, y = t) ;

    return y;
}

int main(int argc, const char * argv[])
{
    cin >> n;
    while (n--)
    {
        ll p, q, b;
        scanf("%lld%lld%lld", &p, &q, &b);

        if (p == 0)
        {
            puts("Finite");
            continue;
        }

        ll g = gcd(p, q);
        q /= g;
        p /= g;
        while (q > 1)
        {
            g = gcd(q, b);
            if (g == 1)
            {
                break;
            }

            while (q % g == 0)
            {
                q /= g;
            }
        }

        if (q == 1)
        {
            puts("Finite");
        }
        else
        {
            puts("Infinite");
        }
    }

    return 0;
}