I have been struggling for three days.
First is the BSGS strategy.
a^x ≡ b (mod m) gcd(a,m)=1
To determine a positive integer n, I have been thinking for a long time why it is sqrt(m).
Assuming the use of the ordinary method, brute force x from 0 to the appearance of the answer.
If an already appeared number is assumed:
2^x ≡3 (mod 5)
x=0 (2^x)mod 5=1
x=1 (2^x)mod 5=2
x=2 (2^x)mod 5=4
x=3 (2^x)mod 5=3 Answer, but if we continue to search
x=4 (2^x)mod 5=1 Found repetition
x=5 (2^x)mod 5=2 And this expression is also equal to (1*2)mod 5, which is equal to the two initial conditions
It means entering a loop.
So the highest number of steps is also only m, under the condition of <=m, it is certain to find repetition and enter the loop.
At most, 0~m-1 all have positions that are just filled.
So BSGS also uses this method, but it is only calculated using the reciprocal of the modulus.
BS requires time is brute force O(n)
GS only requires O(m/n) because it uses the idea of radix sorting.
So the fastest way is n=sqrt(m), O(sqrt(m))
A headache problem......
//============================================================================
// Name : Discrete Logging.cpp
// Date : 2013/4/19 下午12:20:32
// Author : GCA
//============================================================================
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <climits>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <cctype>
#include <utility>
using namespace std;
#ifdef ONLINE\_JUDGE
#define ll "%lld"
#else
#define ll "%I64d"
#endif
typedef unsigned int uint;
typedef long long int Int;
#define Set(a,s) memset(a,s,sizeof(a))
#define Write(w) freopen(w,"w",stdout)
#define Read(r) freopen(r,"r",stdin)
#define Pln() printf("\\n")
#define I\_de(x,n)for(int i=0;i<n;i++)printf("%d ",x\[i\]);Pln()
#define De(x)printf(#x"%d\\n",x)
#define For(i,x)for(int i=0;i<x;i++)
#define CON(x,y) x##y
#define Pmz(dp,nx,ny)for(int hty=0;hty<ny;hty++){for(int htx=0;htx<nx;htx++){\\
printf("%d ",dp\[htx\]\[hty\]);}Pln();}
#define M 55
#define PII pair<int,int\>
#define PB push\_back
#define oo INT\_MAX
#define Set\_oo 0x3f
#define Is\_debug true
#define debug(...) if(Is\_debug)printf("DEBUG: "),printf(\_\_VA\_ARGS\_\_)
#define FOR(it,c) for(\_\_typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define eps 1e-6
bool xdy(double x,double y){return x>y+eps;}
bool xddy(double x,double y){return x>y-eps;}
bool xcy(double x,double y){return x<y-eps;}
bool xcdy(double x,double y){return x<y+eps;}
int min3(int x,int y,int z){
int tmp=min(x,y);
return min(tmp,z);
}
int max3(int x,int y,int z){
int tmp=max(x,y);
return max(tmp,z);
}
map<Int,Int> mid;
Int p,b,n;
Int x,y;
Int exgcd(Int a,Int b){
if(!b){
x=1;y=0;
return a;
}
Int tmp=exgcd(b,a%b);
Int xx=x;
x=y;
y=xx-(a/b)\*y;
return tmp;
}
Int inverse(Int a,Int m){
exgcd(a,m);
x=(x+m)%m;
Int lx=x;
// debug("%d\\n",lx);
return lx;
}
Int solve(){
Int sqrtp=sqrt(p);
Int tmp=1;
for(Int i=0;i<sqrtp;i++){
if(tmp==n)return i;
if(!mid.count(tmp))mid\[tmp\]=i;
tmp=(tmp\*b)%p;
}
Int inv=inverse(tmp,p);
for(Int i=0;i<sqrtp+1;i++){
if(mid.count(n))return i\*sqrtp+mid\[n\];
n=(n\*inv)%p;
}
return -1;
}
int main() {
ios\_base::sync\_with\_stdio(0);
while(~scanf("%lld%lld%lld",&p,&b,&n)){
Int ans=solve();
if(ans!=-1){
printf("%lld\\n",ans);
}else{
printf("no solution\\n");
}
mid.clear();
}
}