[bzoj 3031] 理科男

题意

给定一个 $K$ 进制分数 $frac{A}{B}$ 求是否是循环小数，且求出循环节长度

题解

暴力

il int find(int p){
    int head=last[p%mod];
    while(head&&pr[head].p!=p)head=pr[head].next;
    if(!head)head=++siz;
    return head;
}

int main(){
    T=gi;
    while(T--){siz=0;memset(last,0,sizeof(last));
        ll p,q,k;
        p=gi;q=gi;k=gi;
        ll d=gcd(p,q);        
        p/=d;q/=d;
        p%=q;
        for(int i=1;;i++){
            p*=k;
            if(!(p%q)){
                printf("%d 0
",i);
                break;
            }
            int t=find(p);
            if(!pr[t].id)pr[t]=(data){i,p};
            else{
                printf("%d %d
",pr[t].id-1,i-pr[t].id);
                break;
            }
            p%=q;
        }
    }
    return 0;
}

正解：

首先设 $a_1=A$ 一个序列 $r$ , $r_i$ 表示原数小数点后i位，那么 $r_1=$lfloor${k$ imes$A/B}$ floor$$

然后余数 $a_i=K*a_{i-1}~mod~B$

且 $r_i=$lfloor$K$ imes$a_i/B$ floor$$

上面暴力是计算到 $a_p=a_q$ 这样一对的时候停止

那么考虑a的性质如果 $(B,K)=1$ ，那么 $(a_i,B)=1$

设 $K'K$equiv$1(mod~B)$

如果 $p eq1$ 那么 $a_{p-1}=K'$ imes$a_p~mod~B=K'$ imes$a_q~mod~B=a_{q-1}$

就是出现了更早的重复，所以最早的重复肯定是在p=1，说明这样形式的只有纯循环小数

如果满足 $a_q=a_1$ imes$K^{q-1}~mod~B=a_1$

于是 $K^{q-1$equiv$1~(mod~B)$

然后就是求一个K模B的阶的问题。

阶很好求。。

如果 $(B,K)>1$

那么设 $B'=B/(a_2,B)$

$a_i'=a_i/(a_2,B)$

重复这个过程，然后直到 $(B',K)=1$ 时，做了多少次，前面非循环部分长度就是t,求一遍阶就可以了

#include<queue>
#include<map>
#include<cstdio>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int>Pii;
const int inf=0x7fffffff;
const ll infll=(1ll<<60);
#define dbg(n)    cerr<<#n"="<<n<<endl;
#define Ri register int
#define gc getchar()
#define il inline
il ll read(){
    bool f=true;
    register ll x=0;char ch;
    while(!isdigit(ch=gc))
        if(ch=='-')f=false;
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=gc;
    }
    return f?x:-x;
}
#define X first
#define Y second
#define gi read()
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout);
inline ll gcd(ll a,ll b){
    return b?gcd(b,a%b):a;
}
map<ll,int> Calc(ll x){
    map<ll,int> prime;
    for(int i=2;(ll)i*i<=x;i++)
        if(x%i==0){
            int sum=0;
            while(x%i==0)x/=i,sum++;
            prime[i]=sum;
        }
    if(x>1)prime[x]=1;
    return prime;
}
il ll Euler_phi(ll x,const map<ll,int>& prime){
    ll ans=x;
    for(map<ll,int>::const_iterator i=prime.begin();i!=prime.end();i++)
        if(i->Y)ans=ans/i->X*(i->X-1);
    return ans;
}
il ll Mul(ll a,ll b,ll mod){
    ll ans=0,p=a%mod;
    while(b){
        if(b&1)ans=(ans+p)%mod;
        p=(p+p)%mod;
        b>>=1;
    }
    return ans;
}
il ll Mod(ll a,ll b,ll mod){
    ll ans=1,p=a%mod;
    while(b){
        if(b&1)ans=Mul(ans,p,mod);
        p=Mul(p,p,mod);
        b>>=1;
    }
    return ans;
}
ll A,B,K;
int main(){
    int T;
    cin>>T;
    while(T--){
        A=gi;B=gi;K=gi;
        ll d=gcd(A,B);
        A/=d;B/=d;
        map<ll,int> prime_B=Calc(B),prime_K=Calc(K);
        int M=0;ll tmpB=B;
        for(map<ll,int>::const_iterator  i=prime_K.begin();i!=prime_K.end();i++){
            int p=prime_B[i->X];prime_B[i->X]=0;
            M=max(M,(p+i->Y-1)/i->Y);
            while(p)
                tmpB/=i->X,p--;
        }
        ll R=0;
        if(tmpB!=1){
            ll phi_B=Euler_phi(tmpB,prime_B);
            R=phi_B;
            prime_B=Calc(R);
            for(map<ll,int>::const_iterator i=prime_B.begin();i!=prime_B.end();i++){
                int p=i->Y;
                while(p){
                    if(Mod(K,R/i->X,tmpB)==1)
                        p--,R/=i->X;
                    else break;
                }
            }
        }
        cout<<M<<" "<<R<<endl;
    }
    return 0;
}