牛客周赛round6 T5题解

首先假设 和10互质，那么根据欧拉定理可以得出 一定是的倍数，也就是说必然是的一个循环节（举例，，所以999999一定是7的倍数，999999/7=142857，那么1/7一定是0.142857142857……的循环）。因此最小循环节必然是的因子。我们只需要枚举的每个因子，用快速幂检验一下因子是否满足即可。

对于 和10不互质的情况，我们可以将p乘一个10的幂，和的2或者5的因子约掉后即可满足和10互质了。带来的影响则是等号右边的小数点左移，即产生了“循环节前面的部分”。因此，循环节前面的部分即中2或5的最大因子数。

参考代码：

#include<bits/stdc++.h>
using namespace std;
long long phi(long long x){
    long long i;
    long long res=x;
    for(i=2;i*i<=x;i++){
        if(x%i==0){
            res=res/i*(i-1);
            while(x%i==0)x/=i;
        }
    }
    if(x>1)res=res/x*(x-1);
    return res;
}
long long power(__int128 a,long long b,long long p){
    __int128 res=1;
    while(b){
        if(b&1)res=res*a%p;
        b>>=1;
        a=a*a%p;
    }
    return res;
}
int main(){
    long long p,q,i,c2=0,c5=0;
    cin>>p>>q;
    q/=__gcd(p,q);
    while(q%2==0)q/=2,c2++;
    while(q%5==0)q/=5,c5++;
    if(q==1)return cout<<-1,0;
    long long temp=phi(q);
    long long mi=1e16;
    for(i=1;i*i<=temp;i++){
        if(temp%i==0){
            if(power(10,i,q)==1)mi=min(mi,i);
            if(power(10,temp/i,q)==1)mi=min(mi,temp/i);  
        }
    }
    cout<<max(c2,c5)<<' '<<mi;
}