题解 CF983A 【Finite or not?】

## 题目大意 $T$ 组询问，每次询问 $\frac{n}{m}$ 在 $b$ 进制下是否为循环小数。 ## 题解 先将该分数化简为最简分数，即 $n,m$ 同时除以 $\gcd(n,m)$ 。此时有 $n,m$ 互质。 假定 $\frac{n}{m}$ 在 $b$ 进制下可以表示为有限小数。不妨设小数点后共有 $k$ 位。 于是，我们有： $$\frac{n\times b^k}{m} \in \Bbb N^* , \iff m \ | \ n\times b^k ,\iff m \ | \ b^k$$ 假设 $p$ 为 $m$ 的任意一个质因子。由于 $k$ 可以足够大，因此 $b$ 中至少应该含有一个 $p$ 。于是，问题转化为，$m$ 的每个质因子，都应该是 $b$ 的质因子。考虑如何求解。 由于 $m \le 10^{18}$ ，因此 $m$ 中每个质因子的次数不会超过 $60$ 。我们计算出 $b^{60}$ ，那么它对应质因子的次数必定不小于 $m$ 。于是，该分数可化为循环小数，当且仅当： $$b^{60} \equiv 0 \pmod m$$ 要注意的是，由于题目给出的数字较大，可能需要用快速乘法。 ## 参考代码 ```cpp #include<bits/stdc++.h> #pragma GCC optimize("Ofast") #define up(l,r,i) for(int i=l,END=r;i<=END;++i) #define dn(r,l,i) for(int i=r,END=l;i>=END;--i) using namespace std; typedef long long i64; const int INF =2147483647; i64 qread(){ i64 w=1,c,ret; while((c=getchar())> '9'||c< '0') w=(c=='-'?-1:1); ret=c-'0'; while((c=getchar())>='0'&&c<='9') ret=ret*10+c-'0'; return ret*w; } i64 mul(i64 x,i64 y,i64 p){ i64 r=0,t=x%p; while(y){ if(y&1) r+=t; t<<=1,y>>=1; if(t>=p) t-=p; if(r>=p) r-=p; } return r; } i64 pwr(i64 a,i64 b,i64 p){ i64 r=1,t=a; while(b){ if(b&1) r=mul(r,t,p); t=mul(t,t,p),b>>=1; } return r%p; } int main(){ dn(qread(),1,T){ i64 n=qread(),m=qread(),b=qread(),d=__gcd(n,m); n/=d,m/=d; puts(pwr(b,60,m)?"Infinite":"Finite"); } return 0; } ```