【poj2417】Discrete Logging

Time Limit: 5000MS Memory Limit: 65536K

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 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 1 5 2 2 5 2 3 5 2 4 5 3 1 5 3 2 5 3 3 5 3 4 5 4 1 5 4 2 5 4 3 5 4 4 12345701 2 1111111 1111111121 65537 1111111111

Sample Output

0 1 3 2 0 3 1 2 0 no solution no solution 1 9584351 462803587

Solution

一道BSGS模板题啦，留作纪念……

Code

#include<stdio.h> #include<algorithm> #include<iostream> #include<cstdlib> #include<cstring> #include<cmath> using namespace std; typedef long long ll; const ll mod=76543; ll P,B,N,ans,top,hs[mod],id[mod],Last[mod],Next[mod]; void Insert(ll x,ll y) { ll z=x%mod; hs[++top]=x,id[top]=y,Next[top]=Last[z],Last[z]=top; } ll Find(ll x) { ll z=x%mod; for(ll i=Last[z];i;i=Next[i]) if(hs[i]==x) return id[i]; return -1; } ll BSGS(ll a,ll b,ll c) { if(b==1) return 0; ll m=ceil(sqrt(c)),j=1,t=1,k; for(ll i=0;i<m;i++,j=j*a%c) Insert(j*b%c,i); for(ll i=m;i<=c;i+=m) if(~(k=Find(t=t*j%c))) return i-k; return -1; } int main() { while(~scanf("%lld%lld%lld",&P,&B,&N)) { top=0,memset(Last,0,sizeof(Last)); ans=BSGS(B,N,P); if(~ans) printf("%lld\n",ans); else puts("no solution"); } return 0; }