Codeforces483Div1 983A Finite or not?

题意：

给出N次询问，每次询问十进制下的p/q能否在b进制下表示成有限小数。
$N\leq 10^5,p,q,b\leq 10^{18}$

分析：

在b进制下，该数若能被表示为有限小数，则必须满足：
$p*b^k\equiv 0 (mod \space q)$，其中$k\in [0,∞)$
在p，q互质的情况下，要使得$\{p的质因子集合\}\subseteqq\{b的质因子集合\}$
判断的方法有很多
其中一个方法是：不停地取$g=gcd(p,b)$，令$p=p/g$
若当p不为1时，g=1,则说明不满足，否则就一定满足。考虑到卡常，每次计算后令b=g。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define SF scanf
#define PF printf
#define MAXN 100010
using namespace std;
typedef long long ll;
int n;
ll p,q,b;
ll gcd(ll x,ll y){if(y==0)return x;return gcd(y,x%y);
}
int main(){SF("%d",&n);for(int i=1;i<=n;i++){SF("%I64d%I64d%I64d",&p,&q,&b);if(p==0){PF("Finite\n");continue;}ll g=gcd(p,q);p/=g;q/=g;ll t=b;while(q!=1ll){t=gcd(q,t);if(t==1ll)break;q/=t;}if(q==1ll)PF("Finite\n");elsePF("Infinite\n");}
}