51NOD 1038：X^A Mod P——题解

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1038

X^A mod P = B，其中P为质数。给出P和A B，求< P的所有X。

找了半天找到了一道模板题，死嗑了一晚上对着题解写完了。

道理应该都懂吧……不懂我也懒的再说一遍了，看其他人博客吧：https://blog.csdn.net/dreamzuora/article/details/52744666

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cctype>
#include<cstdio>
#include<vector>
#include<cmath>
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;
}
vector<int>v;
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;
}
bool pan(int g,int p){
    for(int i=0;i<v.size();i++){
        if(qpow(g,(p-1)/v[i],p)==1)return 0;
    }
    return 1;
}
int primitive(int p){
    int res=p-1;v.clear();
    for(int i=2;i*i<=res;i++){
        if(res%i==0){
            v.push_back(i);
            while(res%i==0)res/=i;
        }
    }
    if(res!=1)v.push_back(res);
    for(int i=1;;i++){
        if(pan(i,p))return i;
    }
}
vector<int>X;
void solve(int p,int a,int b){
    X.clear();
    int g=primitive(p)%p;
    int t=BSGS(g,b,p);
    if(t==-1)return;
    int A=a,B=p-1,C=t,x,y;
    int d=exgcd(A,B,x,y);
    if(C%d)return;
    x=(ll)x*(C/d)%B;
    int delta=B/d;
    for(int i=0;i<d;i++){
        x=((x+delta)%B+B)%B;
        X.push_back(qpow(g,x,p));
    }
    sort(X.begin(),X.end());
    X.erase(unique(X.begin(),X.end()),X.end());
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int p,a,b;
        scanf("%d%d%d",&p,&a,&b);
        solve(p,a,b);
        if(!X.size()){puts("No Solution");continue;}
        else{
            for(int i=0;i<X.size();i++)printf("%d ",X[i]);
            puts("");
        }
    }
    return 0;
}

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。 　　　　　　　　　　　　　　+

+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/ +

+++++++++++++++++++++++++++++++++++++++++++