It took me three days
First is the BSGS strategy
a^x ≡ b (mod m) gcd(a,m)=1
And to determine a positive integer n, I thought for a long time about why it is sqrt(m)
Assuming using the ordinary method, brute force solving x from 0 until an answer appears
A number that has already appeared 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 I continue to find
x=4 (2^x)mod 5=1 Found a repeat
x=5 (2^x)mod 5=2 And this expression is also equal to (1*2)mod 5, which is also equal to the initial two cases
It means entering a loop
So the maximum number of steps is only m, under the condition of <=m, it is certain to find a repeat, and enter a loop
At most, there are positions from 0 to m-1 that just fill up perfectly
So BSGS also uses this method, but it just calculates using the modular inverse
BS requires time that 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 brain-teasing problem......
//============================================================================
// Name : Discrete Logging.cpp
// Date : 2013/4/19 12:20:32 PM
// 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();
}
}