[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\n",i);

                break;

            }

            int t=find(p);

            if(!pr[t].id)pr[t]=(data){i,p};

            else{

                printf("%d %d\n",pr[t].id-1,i-pr[t].id);

                break;

            }

            p%=q;

        }

    }

    return 0;

}

正解：

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

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

且 $r_i=$\lfloor$K$\times$a_i/B$\rfloor$$

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

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

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

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

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

如果满足 $a_q=a_1$\times$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;

}

巴特西

[bzoj 3031] 理科男

题意

题解

最新文章

热门文章