题目链接

题目大意是：

给你三个整数，p,q,b。其中p/q是个分数。该题目要求你给出p/q在b进制下是否是个无限小数。

解题思路：

首先我们需要知道小数转化为二进制。假定有分数a/b(a<b),要将它转化为k进制。我们需要取a * k / b为第

一位。然后让a = a * k % b.重复以上步骤，直到a* k % b == 0;

a * k % b 一直不等于0那么就说明这个分数是无限小数。

如果判断 a * k % b 一直不等于0在代码层面是可行的，但是时间复杂度复杂度会比较高，而且从逻辑上说

也比较麻烦。

我们可以换一种思路，我们只要判断a * k % b 在小数转化为二进制这个过程是否能等于0即可。

具体该题思路就很清晰了：

我们可以先将p/q化简得到化简后的p/q.如果1/q是无限小数，那么他乘上p后也是个无限小数。所以我们发

现一个分数在b进制下是否是无限小数只跟这个分数化简后的分母和b有关。

根据前面的推论，我们只需判断是否存在一个i使得b ^ i % q == 0 即可。、

很容易看出存在b ^ i % q == 0的充分条件是b必须包含q的所有质因子。

如当b = 1386,q = 252时，b的质因子有2 * 3 * 3 * 7 * 11。 q的质因子有 2 * 2 * 3 * 3 * 7.

此时我们就可以说b 包含q的所有质因子(注意此时说的包含是指种类包含)。

代码如下：

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define mmset(a,b) memset(a,b,sizeof(a))
#define ll long long
using namespace std; 
ll gcd(ll a, ll b)
{
	return b == 0 ? a : gcd(b,a % b);
} 
/*
2
6 12 10
4 3 10
outputCopy
Finite
Infinite
inputCopy
4
1 1 2
9 36 2
4 12 3
3 5 4
outputCopy
Finite
Finite
Finite
Infinite
*/
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		ll p,q,b;
		scanf("%lld %lld %lld",&p,&q,&b);
		ll g = gcd(q,p);
		q /= g, p /= g;
		if(p == 0 || q == 1) 
		{
			printf("Finite\n") ;
		}
		else
		{
			int g;
			while(q != 1&&b != 1)
			{
				b = gcd(q,b);
				q /= b;
			}
			if(q == 1)
			{
				printf("Finite\n");
			}
			else
			{
				printf("Infinite\n");
			}
		}
	}
	
	
	return 0;
}