Finite or not?

wjh15101051's space

卧薪尝胆，厚积薄发。

Finite or not?

Date: Thu Sep 20 15:02:34 CST 2018

In Category: NoCategory

Description：

有 $n$ 组数据，每一组数据读入一个分数的分子 $p$ 、分母 $q$ 和进制 $b$ ,求在 $b$ 进制下 $\frac{p}{q}$ 是否为有限小数。

$1\le n \le 10^5,1\le p,q,b\le 10^{18}$

Solution：

先把 $p$ 和 $q$ 约分，然后这时只有 $q$ 的所有质因数都是 $b$ 的质因数时才合法，于是不停除 $gcd$ 即可，有一些优化就是可以每次把 $b$ 变成 $gcd$ ，每次除掉好多 $gcd$ 。

复杂度上界是 $O(10^5\log^210^{18})$ ，但实际上跑不满。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

typedef long long ll;

inline ll read()

{

	register ll res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

ll p,q,b;

ll gcd(ll a,ll b){return (b == 0 ? a : gcd(b,a % b));}

int main()

{

	int n;

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)

	{

		p = read();q = read();b = read();

		ll g = gcd(p,q);

		p /= g;q /= g;

		while(q != 1 && (g = gcd(q,b)) != 1)

		{

			while(q % g == 0)q /= g;

			b = g;

		}

		if(q == 1)puts("Finite");

		else puts("Infinite");

	}

	return 0;

}

In tag: 数学-最大公约数与最小公倍数

wjh15101051