1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| #include<bits/stdc++.h>
using namespace std;
long long mod,n,k;
map<long long,int>m;
int ans=0x7fffffff;
inline void BSGS()
{
int t=sqrt(mod)+1;
long long sum=k;
long long sum0=1;
m[k]=0;
for(int i=1;i<=t;i++)
{
sum*=n;
sum%=mod;
sum0*=n;
sum0%=mod;
m[sum]=i;
}
sum=1;
for(int i=0;i<=t;i++)
{
if(m.find(sum)!=m.end())
{
if(i*t-m[sum]>=0)
{
cout<<i*t-m[sum];
return ;
}
}
sum*=sum0;
sum%=mod;
}
puts("no solution");
return ;
}
int main()
{
cin>>mod>>n>>k;
BSGS();
return 0;
}
|