给定a,b,p,求最小的非负整数x
满足a^x≡b(mod p)
若无解
请输出“orz”
输入格式:
三个整数,分别为a,b,p
输出格式:
满足条件的非负整数x
输入样例#1:
5 2 7
输出样例#1:
4
pow有误差
数据保证所有变量都在int范围内
bsgs模板问题
解决bsgs的问题,我们首先可以吧题目a^x=b(mod)p转化为a^(i*m)=b*a^j
然后枚举b*a^j,a^(i*m)
暴力求解
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<map>
6 #define LL long long
7 using namespace std;
8 LL a,b,c;
9 map<LL,LL>mp;
10 LL fastpow(LL a,LL p,LL c)
11 {
12 LL base=a;LL ans=1;
13 while(p!=0)
14 {
15 if(p%2==1)ans=(ans*base)%c;
16 base=(base*base)%c;
17 p=p/2;
18 }
19 return ans;
20 }
21 int main()
22 {
23 // a^x = b (mod c)
24 while(scanf("%lld%lld%lld",&c,&a,&b)!=EOF)
25 {
26 LL m=ceil(sqrt(c));// 注意要向上取整
27 mp.clear();
28 if(a%c==0)
29 {
30 printf("no solution\n");
31 continue;
32 }
33 // 费马小定理的有解条件
34 LL ans;//储存每一次枚举的结果 b* a^j
35 for(LL j=0;j<=m;j++) // a^(i*m) = b * a^j
36 {
37 if(j==0)
38 {
39 ans=b%c;
40 mp[ans]=j;// 处理 a^0 = 1
41 continue;
42 }
43 ans=(ans*a)%c;// a^j
44 mp[ans]=j;// 储存每一次枚举的结果
45 }
46 LL t=fastpow(a,m,c);
47 ans=1;//a ^(i*m)
48 LL flag=0;
49 for(LL i=1;i<=m;i++)
50 {
51 ans=(ans*t)%c;
52 if(mp[ans])
53 {
54 LL out=i*m-mp[ans];// x= i*m-j
55 printf("%lld\n",(out%c+c)%c);
56 flag=1;
57 break;
58 }
59
60 }
61 if(!flag)
62 printf("no solution\n");
63 }
64
65 return 0;
66 }