C. Finite or not? Codeforces Round #483 (Div. 2)

传送门

You are given several queries. Each query consists of three integers $p$, $q$ and $b$. You need to answer whether the result of $p/q$ in notation with base $b$ is a finite fraction.

A fraction in notation with base $b$ is finite if it contains finite number of numerals after the decimal point. It is also possible that a fraction has zero numerals after the decimal point.

Input

The first line contains a single integer $n$ ($1\le n\le {10}^5$) — the number of queries.

Next $n$ lines contain queries, one per line. Each line contains three integers $p$, $q$, and $b$ ($0\le p\le {10}^{18}$, $1\le q\le {10}^{18}$, $2\le b\le {10}^{18}$). All numbers are given in notation with base $10$.

Output

For each question, in a separate line, print Finite if the fraction is finite and Infinite otherwise.

Examples

input

Copy

2
6 12 10
4 3 10

output

Copy

Finite
Infinite

input

Copy

4
1 1 2
9 36 2
4 12 3
3 5 4

output

Copy

Finite
Finite
Finite
Infinite

Note

$\frac{6}{12}=\frac{1}{2}=0,5_{10}$

$\frac{4}{3}=1,(3{)}_{10}$

$\frac{9}{36}=\frac{1}{4}=0,{01}_2$

$\frac{4}{12}=\frac{1}{3}=0,1_3$

这个题首先得掌握下十进制小数如何化为二进制小数的思想

传送门

首先如果p是0，那么肯定就是有限的，然后对于p/q可以先对分子分母约分一下，只需要关心1/q是否可以在b进制下被有限

表示即可，因为他俩之间只差了个系数p，也就是说1/q可以被有限表示，那么p/q一定可以被有限表示。

考虑1/q，一定是一个小于等于1的数，考虑吧小数转化为b进制的过程，在上篇博客中已经提到过。最后总结下，就是

如果存在(b^i)(modq)=0，那么就证明可以转化为一个b进制下的有限小数，于是我们判断是否存在这个i即可。

还有一种性质，在十进制如果p/q是分数的最简形式。那么p/q能化成有限小数。当且仅当q的质因数分解形式中只有质因子2和5

(且不能出现其他质因子)(也就是说q的质因子只能出现10的质因子里面出现过的因为只有这样分母才能化成10^n的形式。才能化成小数。）

因此。对于在b进制下的小数p/q只要看看q的质因子是不是都是b的质因子就可以了。用gcd来做。每次都用q去除gcd(q,b)

这样。如果最后q能够变成1.那就说明q的质因子都是b的质因子。

代码如下：

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

LL gcd(LL temp1,LL temp2)
{
	LL minn=temp1,maxn=temp2;
	if(temp1>temp2){
		swap(minn,maxn);
	}
	return minn==0?maxn:gcd(maxn%minn,minn);
}

int main()
{
	int n;
	scanf("%d",&n);
	while(n--){
        LL p,q,b;
        scanf("%I64d%I64d%I64d",&p,&q,&b);
        if(p==0){
        	printf("Finite\n");
        }else{
        	LL ans=gcd(p,q);
        	p/=ans;
        	q/=ans;
        	if(q==1){
        		printf("Finite\n");
        	}else{
        		LL res;
        		while(res=gcd(q,b)>1){
        			LL temp=gcd(q,b);
        			while(q%temp==0){//必须进行优化
        				q/=temp;
        			}
        		}
        		if(q==1){
        			printf("Finite\n");
        		}else{
        			printf("Infinite\n");
        		}
        	}
        }
	}
	return 0;
}