【bzoj2242】: [SDOI2011]计算器 数论-快速幂-扩展欧几里得-BSGS

/* http://www.cnblogs.com/karl07/ */
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <algorithm>
using namespace std;

#define LL long long
int T,K;
LL a,b,p;

LL Q_tim(LL x,LL y,LL p){
    LL ans=0;
    while (y){
        if (y&1) ans=(ans+x)%p;
        x=(x+x)%p;
        y=(y>>1);
    }
    return ans;
}

LL Q_pow(LL x,LL y,LL p){
    LL ans=1;
    while (y){
        if (y&1) ans=ans*x%p;
        x=x*x%p;
        y=(y>>1);
    }
    return ans;
}

void ex_gcd(LL a,LL b,LL &x,LL &y,LL &gcd){
    if (b==0) {gcd=a;x=1;y=0;return;}
    ex_gcd(b,a%b,y,x,gcd);
    y-=x*(a/b);
}

void p2(LL a,LL b,LL p){
    LL x,y,gcd,g,ans=p+1;
    ex_gcd(a,p,x,y,gcd);
    if (b%gcd!=0){ puts("Orz, I cannot find x!"); return;}
    ex_gcd(a/gcd,p/gcd,x,y,g);
    x=x*(b/gcd)%p;
    x=(x+p)%p;
    printf("%lld\n",x);
}

void BSGS(LL a,LL b,LL p){
    if ((a==0 && b!=0) || (a==1 && b!=1)) { puts("Orz, I cannot find x!"); return;}
    LL sz=(LL)ceil(sqrt(p)),inv,e=1;
    map<LL,LL> x;
    x.clear();
    x[1]=0;inv=Q_pow(Q_pow(a,sz,p),p-2,p);
    for (int i=1;i<sz;i++) {e=Q_tim(e,a,p); if (!x.count(e)) x[e]=i;}
    for (int i=0;i<sz;i++) {
        if (x.count(b)) {printf("%lld\n",i*sz+x[b]); return;}
        b=Q_tim(b,inv,p);
    }
    puts("Orz, I cannot find x!");
}

int main(){
    scanf("%d%d",&T,&K);
    for (int i=1;i<=T;i++){
        scanf("%lld%lld%lld",&a,&b,&p);
        if (K==1) printf("%lld\n",Q_pow(a%p,b,p));
        if (K==2) p2(a%p,b%p,p);
        if (K==3) BSGS(a%p,b%p,p);
    }
    return 0;
}