cf984c Finite or not?

一个十进制分数 \(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?

最新文章

热门文章