Discrete Logging
Time Limit:5000MSMemory Limit:65536K
Total Submissions:4011Accepted:1849
Description
Given a prime P, 2 <= P < 231, 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 BL == 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
Hint
The solution to this problem requires a well known result in number theory that is probably expected of you for Putnam but not ACM competitions. It is Fermat’s theorem that states B(P-1) == 1 (mod P)for any prime P and some other (fairly rare) numbers known as base-B pseudoprimes. A rarer subset of the base-B pseudoprimes, known as Carmichael numbers, are pseudoprimes for every base between 2 and P-1. A corollary to Fermat’s theorem is that for any m B(-m) == B(P-1-m) (mod P) .
Source
/* ***********************************************Author:CKbossCreated Time :2015年03月31日 星期二 19时39分34秒File Name:POJ2417.cpp************************************************ */#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <string>#include <cmath>#include <cstdlib>#include <vector>#include <queue>#include <set>#include <map>using namespace std;const int MOD=76543;int hs[MOD],head[MOD],next[MOD],id[MOD],top;void insert(int x,int y){int k=x%MOD;hs[top]=x; id[top]=y; next[top]=head[k]; head[k]=top++;}int find(int x){int k=x%MOD;for(int i=head[k];~i;i=next[i])if(hs[i]==x) return id[i];return -1;}int BSGS(int a,int b,int n){memset(head,-1,sizeof(head));top=1;if(b==1) return 0;int m=sqrt(n*1.0),j;long long x=1,p=1;for(int i=0;i<m;i++,p=p*a%n) insert(p*b%n,i);for(long long i=m;;i+=m){if((j=find(x=x*p%n))!=-1) return i-j;if(i>n) break;}return -1;}int main(){//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);int b,n,p;while(scanf("%d%d%d",&p,&b,&n)!=EOF){int ans=BSGS(b,n,p);if(ans==-1) puts("no solution");else printf("%d\n",ans);}return 0;}
，生活不会永远都困难;祝你爱情蜜甜，事业大进步
