Discrete Logging

Time Limit: 5000MS		Memory Limit: 65536K
Total Submissions: 4624		Accepted: 2113

 

Description

Given a prime P, 2 <= P < 2³¹, an integer B, 2 <= B < P, and an integer N, 1 <= N < P, compute the discrete logarithm of N, base B, modulo P. That is, find an integer L such that 

B

^L

== N (mod P)

Input

Read several lines of input, each containing P,B,N separated by a space.

Output

For each line print the logarithm on a separate line. If there are several, print the smallest; if there is none, print "no solution".

Sample Input

5 2 15 2 25 2 35 2 45 3 15 3 25 3 35 3 45 4 15 4 25 4 35 4 412345701 2 11111111111111121 65537 1111111111

Sample Output

013203120no solutionno solution19584351462803587

 

题意：

a^x = b(mod n) ，求解x(模板题)

 

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 using namespace std; 8 typedef long long ll; 9 typedef long double ld;10 11 using namespace std;12 #define MOD 7654313 int hs[MOD],head[MOD],Next[MOD],id[MOD],top;14 15 void insert(int x,int y)16 {17 int k = x % MOD;18 hs[top] = x,id[top] = y,Next[top] = head[k],head[k] = top++;19 }20 21 int find(int x)22 {23 int k = x % MOD;24 for(int i = head[k];i != -1;i= Next[i])25 {26 if(hs[i] == x)27 return id[i];28 }29 return -1;30 }31 32 int BSGS(int a,int b,int n)33 {34 memset(head,-1,sizeof(head));35 top = 1;36 if(b == 1)37 return 0;38 int m = sqrt(n*1.0),j;39 long long x = 1,p =1;40 for(int i = 0;i < m;i++,p = p*a%n)41 insert(p*b%n,i);42 for(ll i = m;;i+=m)43 {44 if((j = find(x = x*p % n)) != -1) return i-j;45 if(i > n) break;46 }47 return -1;48 }49 50 int main()51 {52 int p,b,n;53 while(scanf("%d%d%d",&p,&b,&n) != EOF)54 {55 int ans = BSGS(b,n,p);56 if(ans == -1)57 printf("no solution\n");58 else59 printf("%d\n",ans);60 }61 return 0;62 }