首页 > > 程序设计 > C/C++ >

U9249 【模板】BSGS

2018-06-17 22:35:09来源：未知阅读 ()

题目描述

给定a,b,p，求最小的非负整数x

满足a^x≡b(mod p)

若无解

请输出“orz”

输入输出格式

输入格式：

三个整数,分别为a,b,p

输出格式：

满足条件的非负整数x

输入输出样例

输入样例#1：

5 2 7

输出样例#1：

说明

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 }