U9249 【模板】BSGS-白红宇

U9249 【模板】BSGS

阅读量：6508 次

发布时间：2019-06-24

本文共 1281 字，大约阅读时间需要 4 分钟。

题目描述

给定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
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
          6 #define LL long long  7 using namespace std; 8 LL a,b,c; 9 map
          
           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^j35 for(LL j=0;j<=m;j++) // a^(i*m) = b * a^j36 {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-j55 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 }