CF984 C. Finite or not?【数论/GCD】

【链接】：CF

【题意】：n组样例，对于每组样例，给你三个数p q b，问你p/q在b进制下是不是一个有限小数，是的话输出Finite，否则输出Infinite。

【分析】：b的过程是对q约分，那么只要b包含q全部的因子即可。考虑1/q，一定是一个小于等于1的数，考虑将小数转化为b进制的过程，每次将小数乘以b然后取整数部分，直到这个小数变成了0，也就是说如果某个小数1/q在b进制下可以被有限表示。

因此。对于在b进制下的小数p/q，只要看看q的质因子是不是都是b的质因子就可以了,显然可以用gcd来搞。每次都用q去除gcd(q,b)。如果最后q能够变成1.那就说明q的质因子都b的质因子。(gcd本质上就是两个数相同质因子中取指数较小的那个,然后全都乘起来）

但不要每次都重新获取q,b的gcd。用上次的结果尝试继续除就好。

【代码】：

#include <bits/stdc++.h>

#define ll long long

#define pb push_back

#define inf 0x3f3f3f3f

#define pll pair<ll,ll>

#define rep(i,a,b) for(int i=a;i<=b;i++)

#define rep1(i,a,b) for(int i=a;i>=b;i--)

#define rson rt<<1|1,m+1,r

#define lson rt<<1,l,m

using namespace std;

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        ll p,q,b;

        scanf("%lld%lld%lld",&p,&q,&b);

        ll g=__gcd(p,q);

        p/=g;

        q/=g;

        if(p==0||q==1){

            printf("Finite\n");

            continue;

        }

        while(q!=1&&b!=1)

        {

            b=__gcd(q,b);

            q/=b;

        }

        if(q==1) printf("Finite\n");

        else printf("Infinite\n");

    }

}

/*

2

6 12 10

4 3 10

4

1 1 2

9 36 2

4 12 3

3 5 4

*/

巴特西

CF984 C. Finite or not?【数论/GCD】

最新文章

热门文章