BSGS是解决\(a^{l}\equiv b(\mod p)\)已知\(a\)、\(b\)、\(p\)的情况下求最小的非负整数\(l\)的算法。
设$m=\left \lceil \sqrt{p} \right \rceil $, \(l=x\times m-y(0\le x< m,0\le y< m)\)
则\(a^{x\times m}\equiv b\times a^{y}(\mod p)\)
枚举y,用map查找到对应的最小的x,求出l的最小值。
代码:
#include<iostream>
#include<cmath>
#include<map>
using namespace std;
int p,b,n;
int m;
map<int,int> f;
long long ksm(long long x,long long y){
if(y==0){
return 1;
}
long long ans=ksm(x,y/2);
ans=ans*ans%p;
if(y%2==1){
ans=ans*x%p;
}
return ans;
}
int main(){
cin>>p>>b>>n;
if(n==1){
cout<<0;
return 0;
}
m=sqrt(p);
m+=(m*m!=p);
for(int i=m-1;i>=1;i--){
f[ksm(b,i*m)]=i;
}
int l=p;
for(int i=0;i<m;i++){
int w=f[n*ksm(b,i)%p];
if(w!=0){
l=min(l,w*m-i);
}
}
if(l==p){
cout<<"no solution";
return 0;
}
cout<<l;
return 0;
}
标签:int,小步,long,times,算法,ans,ksm,include,BSGS
From: https://www.cnblogs.com/z-2-we/p/17054037.html