BZOJ 2219: 数论之神

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=2219

N次剩余+CRT。。。

就是各种奇怪的分类讨论。。

#include<cstring>

#include<iostream>

#include<cstdio>

#include<map>

#include<cmath>

#include<algorithm>

#define rep(i,l,r) for (int i=l;i<=r;i++)

#define down(i,l,r) for (int i=l;i>=r;i--)

#define clr(x,y) memset(x,y,sizeof(x))

#define maxn 50050

#define inf 2000000000

using namespace std;

int a,b,k,p,t,ans;

map<int,int> mp;

int read(){

    int x=,f=; char ch=getchar();

    while (!isdigit(ch)) {if (ch=='-') f=-; ch=getchar();}

    while (isdigit(ch)) {x=x*+ch-''; ch=getchar();}

    return x*f;

}

int Pow(int x,int y){

    int ans=;

    while (y){

        if (y&) ans=1LL*ans*x;

        x=1LL*x*x; y>>=;

    }

    return ans;

}

int Pow(int x,int y,int mo){

    int ans=; while (y){

        if (y&) ans=1LL*ans*x%mo;

        x=1LL*x*x%mo; y>>=;

    }

    return ans;

}

int divs[maxn],dtot;

int groot(int p){//是对于p-1的每一个素因子a去检查(p-1)/a！！

    dtot=;

    int q=p-;

    for (int i=;i*i<=q;i++){

        if (q%i==) {

            divs[++dtot]=i;

            if (i*i!=q) divs[++dtot]=q/i;

        }

    }

    for (int i=;i<p;i++){

        int ok=;

        rep(j,,dtot) if (Pow(i,divs[j],p)==) {ok=;break;}

        if (!ok) return i;

    }

}

int exgcd(int a,int b,int &x,int &y){

    if (b==) {

        x=; y=; return a;

    }

    int d=exgcd(b,a%b,y,x);

    y-=a/b*x;

    return d;

}

int gcd(int a,int b){

    if (b==) return a;

    return gcd(b,a%b);

}

int NI(int a,int b){

    int x,y;

    exgcd(a,b,x,y);

    return (x%b+b)%b;

}

int bsgs(int a,int b,int p){

    mp.clear();

    int m=sqrt(p)+,mul,tmp;

    int now=; rep(i,,m-) {if (!mp.count(now)) mp[now]=i; now=1LL*now*a%p;}

    now=; mul=Pow(a,m,p);

    rep(i,,m-){

        tmp=1LL*b*NI(now,p)%p;

        if (mp.count(tmp)) return mp[tmp]+i*m;

        now=1LL*now*mul%p;

        if (now==) break;

    }

    return inf;

}

int solve(int a,int b,int p,int d){

    int pd=Pow(p,d);

    b=b%pd;

    if (b==) return Pow(p,d-((d-)/a+));

    else {

        int bet=;

        while (b%p==) bet++,b/=p;

        if (bet%a!=) return ;

        int tt=bet/a;

        int g=groot(p),phi=pd-pd/p;

        int ind=bsgs(g,b,pd);

        int d=gcd(a,phi);

        if (ind%d==) return d*Pow(p,(a-)*tt);

        else return ;

    }

}

int main(){

    t=read();

    while (t--){

        a=read(); b=read(); k=read();

        p=*k+;

        ans=;

        for (int i=;i*i<=p&&ans;i++) if ((p%i)==) {

            int now=; while ((p%i)==) p/=i,now++;

            ans=ans*solve(a,b,i,now);

        }

        if (p!=&&ans) ans=ans*solve(a,b,p,);

        printf("%d\n",ans);

    }

    return ;

}