Codeforces Round #483 (Div. 2) [Thanks, Botan Investments and Victor Shaburov!] C. Finite or not?
You are given several queries. Each query consists of three integers pp, qq and bb. You need to answer whether the result of p/qp/qin notation with base bb is a finite fraction.
A fraction in notation with base bb 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.
The first line contains a single integer nn (1≤n≤1051≤n≤105) — the number of queries.
Next nn lines contain queries, one per line. Each line contains three integers pp, qq, and bb (0≤p≤10180≤p≤1018, 1≤q≤10181≤q≤1018, 2≤b≤10182≤b≤1018). All numbers are given in notation with base 1010.
For each question, in a separate line, print Finite if the fraction is finite and Infinite otherwise.
2 6 12 10 4 3 10
Finite Infinite
4 1 1 2 9 36 2 4 12 3 3 5 4
Finite Finite Finite Infinite
612=12=0,510612=12=0,510
43=1,(3)1043=1,(3)10
936=14=0,012936=14=0,012
412=13=0,13412=13=0,13
题意：问p/q在b进制下能不能表示为有限位
思路：
若可以转化为有限位，q|p*b^k。分解质因数，p/gcd(q,p)，那么p,q互质。q|p*b^k等价于q|b^k。那么q所有质因数都包含在b里。
本质是唯一分解定理的运用
#include<bits/stdc++.h>
#define PI acos(-1.0)
#define pb push_back
#define F first
#define S second
#define debug puts
using namespace std;
typedef long long ll;
const int N=3e5+5;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;
map<ll,ll> mp;
ll gcd(ll a,ll b){
if(a<b) swap(a,b);
return b==0?a:gcd(b,a%b);
}
int main(void){
ll n,p,q,b;
cin >>n;
while(n--){
scanf("%I64d%I64d%I64d",&p,&q,&b);
ll GCD=gcd(p,q);
p/=GCD,q/=GCD;
while(1){
GCD=gcd(b,q);
if(GCD==1) break;
while(q%GCD==0) q/=GCD;
}
if(q==1) printf("Finite\n");
else printf("Infinite\n");
}
return 0;
}