//POJ这题用map会TLE，自己造hash，而且要求最小的x；暴力枚举；
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 using namespace std; 10 typedef long long ll; 11 const int N=63335; 12 int myhash[65000],tot; 13 int p,a,b; 14 int quipow(int a,int n) 15 { 16 ll ans=1%p; 17 while(n) 18 { 19 if(n&1)ans=1ll*ans*a%p; 20 n>>=1; 21 a=1ll*a*a%p; 22 } 23 return ans; 24 } 25 struct edge{ 26 int val,next,pos; 27 }e[65000]; 28 void add(int a,int pos) 29 { 30 int key=a%N; 31 e[tot]=(edge){a,myhash[key],pos}; 32 myhash[key]=tot++; 33 34 } 35 vector<int> fd(int a) 36 { 37 int key=a%N,ans=65000; 38 vector<int>f; 39 for(int i=myhash[key];~i;i=e[i].next) 40 if(e[i].val==a)f.push_back(e[i].pos); 41 return f; 42 } 43 int BSGS(int a,int b) 44 { 45 memset(myhash,-1,sizeof(myhash)); 46 tot=0; 47 b%=p; 48 int t=sqrt(p)+1; 49 for(int j=0;j<=t-1;j++) 50 { 51 int val=1ll*b*quipow(a,j)%p; 52 add(val,j); 53 } 54 55 56 if(a==0)return b==0?1:-1; 57 a=quipow(a,t); 58 int ans=INT_MAX; 59 for(int j=0;j<=t;j++) 60 { 61 int val=1ll*quipow(a,j); 62 vector<int>f=fd(val); 63 if(f.size()) 64 { 65 for(int i=0;i) 66 { 67 if(j*t-f[i]>=0)ans=min(ans,j*t-f[i]); 68 } 69 } 70 71 } 72 return ans==INT_MAX?-1:ans; 73 } 74 int main() 75 { 76 77 while(~scanf("%d%d%d",&p,&a,&b)) 78 { 79 int t=BSGS(a,b); 80 if(t==-1)printf("no solution\n"); 81 else printf("%d\n",t); 82 } 83 return 0; 84 }