题目链接:Luogu P3846 [TJOI2007]可爱的质数

代码:

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
#include<cstdio>
#include<map>
#include<cmath>
using namespace std;
map<long long, int> ma;
long long quickPow(long long a, long long b, long long p){
long long ans = 1;
while(b>0){
if(b&1) ans = ans*a%p;
a = a*a%p;
b >>= 1;
}
return ans;
}
int main(){
long long p, b, n, m, now, t;
scanf("%lld %lld %lld", &p, &b, &n);
if(!b%p){
printf("no solution");
return 0;
}
m = ceil(sqrt(p));
now = n%p, ma[now] = 0;
for(int j = 1; j <= m; ++j)
now = now*b%p,
ma[now] = j;
now = 1;
t = quickPow(b, m, p);
for(int i = 1; i <= m; ++i){
now = now*t%p;
if(ma.count(now)&&ma[now]){
int ans = i*m-ma[now];
printf("%lld", (ans%p+p)%p);
return 0;
}
}
printf("no solution");
return 0;
}

 评论