[SPOJ MOD]【扩展Baby step Giant step】

【地址】https://www.spoj.pl/problems/MOD/

【题目大意】

给定a,p,c让你求满足 a^x = c (mod p)的最小非负整数解

无解输出No solution。

【算法分析】

http://hi.baidu.com/edwardmj/blog/item/c72a7c02eb9a8395e950cdf6.html

其实和这题是一模一样的，但是我当时写的太庛了。现在终于写了一个跑得挺快的。

可以作模板了……

【Result】

12009-02-26 23:07:56Robert Gerbicz accepted 1.64 2.7M

C++

4.0.0-8

22009-08-16 16:34:18Tony Beta Lambda accepted 1.70 2.8M

C

32010-07-27 09:20:10rita accepted 2.19 2.6M

C

42011-02-11 10:09:04cwj accepted
edit  run 2.31 3.6M

C++

4.3.2

52011-01-10 10:46:22aekdycoin accepted 2.37 3.5M

C++

4.3.2

62010-05-02 13:18:58sevenkplus accepted 2.84 4.2M

C++

4.0.0-8

72010-07-22 11:24:18●rz accepted 3.02 4.2M

C++

4.0.0-8

82011-01-10 10:13:54aekdycoin accepted 3.10 4.2M

C++

4.0.0-8

92010-02-20 22:31:12Peter Ondrúška accepted 3.35 2.6M

C++

4.0.0-8

102009-09-07 12:46:20watashi accepted 3.65 2.7M

C++

4.0.0-8

【CODE】

#include #include #include #include #include using namespace std;
typedef long long lld;
const int Size=65535;
struct Hashmap{
       struct edge{int y,L;edge *next;}*ls[Size+1],g[Size+10];
       int e;
       void init(){e=0; memset(ls,0,sizeof(ls));}
       void clear(){
            for (int i=0;i            e=0;
       }
       inline
       void add(int y,int L){
            if (Find(y)!=-1) return;
            g[e].y=y; g[e].L=L;
            g[e].next=ls[y&Size];
            ls[y&Size]=&g[e++];
       }
       inline
       int Find(int y){
           for (edge *t=ls[y&Size];t;t=t->next)
             if (t->y==y) return t->L;
           return -1;
       }
}Hash;

int Power_Mod(lld a,int b,int p){
     lld ret=1%p;
     while (b){
          if (b&1) ret=ret*a%p;
          a=a*a%p;
          b>>=1;
     }
     return ret;
}
int gcd(const int a,const int b){return b?gcd(b,a%b):a;}
int Extend_gcd(const int a,const int b,int &x,int &y){
    if (!b){
      x=1;
      y=0;
      return a;
    }
    int ret,t;
    ret=Extend_gcd(b,a%b,x,y);
    t=x; x=y; y=t-a/b*y;
    return ret;
}

int Get(int x,int p,int mul){
    int tx,ty,ret;
    Extend_gcd(x,p,tx,ty);
    ret=(lld)tx*mul%p;
    return ret<0?ret+p:ret;
}

int Baby_Step_Giant_Step(int a,int c,int p){
    if (c>=p) return -1;
    Hash.clear();
    a%p;
    lld tmp,x;
    int i,s,g,plus,Giant_Step;
    for (i=0,tmp=1%p;i<=100;tmp=tmp*a%p,i++) if (tmp==c) return i;
    for (x=1%p,plus=0;(g=gcd(a,p))>1;plus++){
        if (c%g) return -1;
        p/=g;
        c/=g;
        x=x*(a/g)%p;
    }
    s=(int)(sqrt(p)+1e-8);
    for (tmp=1%p,i=0;i    for (i=plus,Giant_Step=Power_Mod(a,s,p);i<=p;i+=s,x=x*Giant_Step%p)
      if ( (g=Hash.Find( Get(x,p,c) )) !=-1 ) return g+i;
    return -1;
}

int main(){
    Hash.init();
    int a,c,p;
    for (;;){
        cin >> a >> p >> c;
        if (a+p+c==0) break;
        c%=p;
        int ans=Baby_Step_Giant_Step(a,c,p);
        if (ans==-1) puts("No Solution");
                else cout << ans << "n";
    }
}