CF-Codeforces Round #483 (Div. 2)-C-Finite or not?

时间:2022-06-03 05:16:00

ACM模版

描述

CF-Codeforces Round #483 (Div. 2)-C-Finite or not?

题解

首先求 p q 的最大公约数,为了在十进制下约分,此时我们先考虑十进制的情况什么条件才能有限,最简分数 a b 能化为有限小数的充要条件是分母 b 不含有 2 5 以外的质因数,那么我们可以尝试猜一下, p q b 进制下想要有限的充要条件是 q 不含 b 拆解后的质因数以外的质因数。所以此时我们无需考虑 p ,只用不断去除 q 中的 b 的质因子,如果可以最后把 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;
}