解a^x==b(mod p)的方程,求最小的X值
设x=i*m+j
则方程化为b*(a^-m)^i%p=a^j%p
0<=i,j<m,m=sqrt(p-1)取上整;
算出a^-m后,然后枚举每一个i,二分查找a^j,成功则输出
注意(a^-1)%p=(a^(p-2))%p;则可把小数化为整数
#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<queue>
#include<math.h>
#include<algorithm>
#define M 1000000
using namespace std;
//Baby-step giant-step算法
//a^x==b(mod p)
//记录(j,a^j)
struct nummap
{
int i;
int num;
}num[M];
map<int,int>s;
int cmp(const nummap &a,const nummap&b)
{
return a.num<b.num||a.num==b.num&&a.i<b.i;
}
//计算a^b%c
int BitLength(int x)
{
int d=0;
while(x>0)
{
x>>=1;
d++;
}
return d;
}
int BitAt(int x,int i)
{
return (x&(1<<(i-1)));
}
int find(int a,int b,int c)
{
long long y=1;
for(int i=BitLength(b);i>0;i--)
{
y=(y*y)%c;
if(BitAt(b,i)>0)
y=(y*a)%c;
}
return y%c;
}
//二分找a^j
int findnum(int t,int len)
{
int l=-1,h=len;
while(l+1<h)
{
int mid=(l+h)>>1;
if(num[mid].num<t)
{
l=mid;
}
else h=mid;
}
if(num[h].num==t)return num[h].i;
return -1;
}
int Baby_step_giant_step(int a,int b,int p)
{
int m=(int)ceil(sqrt((double)p-1));//进行取上整
//计算a^0~a^m-1
long long base=1;
int len=0;
num[len].i=0;
num[len++].num=base;
for(int i=0;i<m-1;i++)
{
base*=a;
base%=p;
num[len].i=i+1;
num[len++].num=base;
}
sort(num,num+len,cmp);
//计算(a^-m)%p=((a^-1)%p^m)%p=((a^(p-2)%p)^m)%p;
int am=find(a,p-2,p);//a^-1
am=find(am,m,p);//am^m
long long ret=b;
for(int i=0;i<m;i++)
{
int j=findnum(ret,m);
//it=s.lower_bound(ret);
if(j!=-1){return i*m+j;}
ret*=am;
ret%=p;
}
return -1;
}
int main()
{
freopen("in.txt","r",stdin);
int n,b,p;
while(scanf("%d%d%d",&p,&b,&n)>0)
{
int x=Baby_step_giant_step(b,n,p);
if(x!=-1)printf("%d\n",x);
else printf("no solution\n");
}
}