BZOJ2242：[SDOI2011]计算器——题解

灰太狼 2021-09-20 09:36 290阅读 0赞

[https://www.lydsy.com/JudgeOnline/problem.php?id=2242][https_www.lydsy.com_JudgeOnline_problem.php_id_2242]

[https://www.luogu.org/problemnew/show/P2485][https_www.luogu.org_problemnew_show_P2485]

> 你被要求设计一个计算器完成以下三项任务：
> 
> 1、给定y,z,p,计算Y^Z Mod P 的值；
> 
> 2、给定y,z,p，计算满足xy≡ Z ( mod P )的最小非负整数；
> 
> 3、给定y,z,p，计算满足Y^x ≡ Z ( mod P)的最小非负整数。

大杂烩题：

1操作快速幂。

2操作把y除过去乘法逆元求一下就能出x了，注意判断是否存在乘法逆元。

3操作就是[POJ3243：Clever Y][POJ3243_Clever Y]了。

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<cctype>
    #include<cstdio>
    #include<cmath>
    #include<stack>
    using namespace std;
    typedef long long ll;
    const int N=999979;
    const int M=40005;
    struct HASH{
        int w,to,nxt;
    }h[M];
    int cnt,head[N];
    inline void add(int x,int y){
        int t=x%N;
        for(int i=head[t];i;i=h[i].nxt){
            int v=h[i].to;
            if(v==x){
                h[i].w=y;//记大的 
                return;
            }
        }
        h[++cnt].to=x;h[cnt].w=y;h[cnt].nxt=head[t];head[t]=cnt;
    }
    inline int query(int x){
        int t=x%N;
        for(int i=head[t];i;i=h[i].nxt){
            int v=h[i].to;
            if(v==x)return h[i].w;
        }
        return -1;
    }
    int gcd(int a,int b){
        return (!b)?a:gcd(b,a%b);
    }
    int exgcd(int a,int b,int &x,int &y){
        if(!b){
            x=1,y=0;
            return a;
        }
        int ans=exgcd(b,a%b,y,x);
        y-=(ll)(a/b)*x;
        return ans;
    }
    int inv(int a,int c){
        int x,y;
        exgcd(a,c,x,y);
        return (x%c+c)%c;
    }
    //a^x=b(mod c);
    int BSGS(int a,int b,int c){
        if(!a){
            if(!b)return 1;
            return -1;
        }
        int tot=0,g,d=1;
        while((g=gcd(a,c))!=1){
            if(b%g)return -1;
            ++tot;b/=g,c/=g;
            d=(ll)d*(a/g)%c;
        }
        b=(ll)b*inv(d,c)%c;
        cnt=0;memset(head,0,sizeof(head));
        int s=sqrt(c),p=1;
        for(int i=0;i<s;i++){
            if(p==b)return i+tot;
            add((ll)p*b%c,i);
            p=(ll)p*a%c;
        }
        int q=p;
        for(int i=s;i-s+1<c;i+=s){
            int t=query(q);
            if(t!=-1)return i-t+tot;
            q=(ll)q*p%c;
        }
        return -1;
    }
    int qpow(int k,int n,int p){
        int res=1;
        while(n){
            if(n&1)res=(ll)res*k%p;
            k=(ll)k*k%p;
            n>>=1;
        }
        return res;
    }
    int main(){
        int T,k;
        scanf("%d%d",&T,&k);
        while(T--){
            int y,z,p;
            scanf("%d%d%d",&y,&z,&p);
            if(k==1)printf("%d\n",qpow(y,z,p));
            if(k==2){
                if(y%p==0)puts("Orz, I cannot find x!");
                else printf("%lld\n",(ll)z*qpow(y,p-2,p)%p);
            }
            if(k==3){
                y%=p,z%=p;
                int ans=BSGS(y,z,p);
                if(ans==-1)puts("Orz, I cannot find x!");
                else printf("%d\n",ans);
            }
        }
        return 0;
    }

\+++++++++++++++++++++++++++++++++++++++++++

\+本文作者：luyouqi233。 　　　　　　　　　　　　　　+

\+欢迎访问我的博客：[http://www.cnblogs.com/luyouqi233/][http_www.cnblogs.com_luyouqi233] \+

\+++++++++++++++++++++++++++++++++++++++++++

转载于:https://www.cnblogs.com/luyouqi233/p/8991034.html

[https_www.lydsy.com_JudgeOnline_problem.php_id_2242]: https://www.lydsy.com/JudgeOnline/problem.php?id=2242
[https_www.luogu.org_problemnew_show_P2485]: https://www.luogu.org/problemnew/show/P2485
[POJ3243_Clever Y]: http://www.cnblogs.com/luyouqi233/p/8989786.html
[http_www.cnblogs.com_luyouqi233]: http://www.cnblogs.com/luyouqi233/