首页 > 其他 > 详细

cf984c Finite or not?

时间:2018-05-22 16:22:08      阅读:196      评论:0      收藏:0      [点我收藏+]

一个十进制分数 \(p/q\)\(b\) 进制下是有限小数的充要条件是 \(q\) 的所有质因子都是 \(b\) 的质因子。

First, if \(p\) and \(q\) are not coprime, divide them on \(\gcd(p,q)\). Fraction is finite if and only if there is integer \(k\) such that \(q∣p?b^k\). Since \(p\) and \(q\) are being coprime now, \(q∣b^k\) \(\Rightarrow\) all prime factors of \(q\) are prime factors of \(b\).

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
int n;
ll p, q, b;
ll gcd(ll a, ll b){
    return !b?a:gcd(b, a%b);
}
int main(){
    cin>>n;
    while(n--){
        scanf("%I64d %I64d %I64d", &p, &q, &b);
        ll f=gcd(p, q);
        p /= f; q /= f;
        f = gcd(q, b);
        while(f!=1){
            while(q%f==0)   q /= f;
            f = gcd(q, b);
        }
        if(b%q) printf("Infinite\n");
        else    printf("Finite\n");
    }
    return 0;
}

cf984c Finite or not?

原文:https://www.cnblogs.com/poorpool/p/9072588.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!