codeforces 983A Finite or not?

题意：

判断一个分数在某一进制下是否为无限小数。

思路：

首先把这个分数约分，然后便是判断。

首先，一个分数是否为无限小数，与分子是无关的，只与分母有关。

然后，再来看看10进制的分数，可化为有限小数的特点，10为分母可以，2为分母可以，16为分母可以，40为分母可以。。。。

总之，其实全部都与2和5有关，2和5又是10的质因数，所以可以猜想到，如果分母可以分解为进制的质因子的乘积，那么就可以化为有限小数。

所以，就判断q的质因子是否为b的子集。

每次求出q与b的最大公约数g，那么g必须可以全部包含q的质因子，所以q /= g，b = g，然后一直这样做，直到g为1，最后再判断q能否整除b。

代码：

 #include <stdio.h>

 #include <string.h>

 #include <algorithm>

 using namespace std;

 typedef long long ll;

 ll gcd(ll a,ll b)

 {

     if (b == ) return a;

     else return gcd(b,a%b);

 }

 int main()

 {

     int n;

     scanf("%d",&n);

     ll p,q,b;

     while (n--)

     {

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

         ll t = gcd(p,q);

         p /= t;

         q /= t;

         if (p == ) puts("Finite");

         else

         {

             while (b % q)

             {

                 ll g = gcd(b,q);

                 if (g == ) break;

                 b = g;

                 q /= g;

             }

             if (b % q == ) puts("Finite");

             else puts("Infinite");

         }

     }

     return ;

 }

巴特西

codeforces 983A Finite or not?

最新文章

热门文章