囧仙 的博客

囧仙 的博客

题解 CF983A 【Finite or not?】

posted on 2020-08-29 23:01:33 | under 题解 |

题目大意

$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$$

要注意的是,由于题目给出的数字较大,可能需要用快速乘法。

参考代码

#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;
}