BSGS算法+逆元 POJ 2417 Discrete Logging

B^l==N(mod p)

/*BSGS算法+逆元*/
这个主要是用来解决这个题： A^x=B(mod C)(C是质数)，都是整数，已知A、B、C求x。 我在网上看了好多介绍，觉得他们写得都不够碉，我看不懂…于是我也来写一发。 先把x=i*m+j，其中m=ceil(sqrt(C))，（ceil是向上取整）。 这样原式就变为A^(i*m+j)=B(mod C)， 再变为A^j=B*A^(-m*i) (mod C)， 先循环j=~(C-)，把（A^j,j)加入hash表中，这个就是Baby Steps 下面我们要做的是枚举等号右边，从hash表中找看看有没有，有的话就得到了一组i j，x=i*m+j，得到的这个就是正确解。 所以，接下来要解决的就是枚举B*A^(-m*i) (mod C)这一步（这就是Giant Step A^(-m*i)相当于1/(A^(m*i))，里面有除法，在mod里不能直接用除法，这时候我们就要求逆元。 /*百度百科： 若ax≡1 mod f, 则称a关于模f的乘法逆元为x。也可表示为ax≡1(mod f)。
当a与f互素时，a关于模f的乘法逆元有唯一解。如果不互素，则无解。如果f为素数，则从1到f-1的任意数都与f互素，即在1到f-1之间都恰好有一个关于模f的乘法逆元。
*/ 然后我们用超碉的exgcd求逆元，exgcd（扩展欧几里德算法）就是在求AB的最大公约数z的同时，求出整数x和y，使xA+yB=z。算法实现就是gcd加几个语句。
然后我们再来看一下exgcd怎么求逆元：
对xA+yB=z， 变成这样xA = z - yB，取B=C（C就是我们要mod的那个） 推导出 xA % C = z %C 只要 z%C== 时,就可以求出A的逆元x 但用exgcd求完，x可能是负数，还需要这样一下：x=(x%C+C)%C //--exgcd介绍完毕-- 再看我们的题目， exgcd(A^(m*i) , C)=z，当C是质数的时候z肯定为1，这样exgcd求得的x就是逆元了。 因为x就是A^(m*i)的逆元，P/(A^(m*i))=P*x，所以 B*A^(-m*i) = B/(A^(m*i)) = B*x(mod C) 这样我们的式子A^j=B*A^(-m*i) (mod C)的等号右边就有了，就是B*x，就问你怕不怕！ 枚举i，求出右边在hash里找，找到了就返回，无敌！ /*---------分割线-----------------------*/
#include<cmath>
#include<iostream>
using namespace std;
#include<cstdio>
#include<cstring>
#define mod 100007
#define ll long long
struct hash
{
ll a[mod+],v[mod+];
hash(){memset(a,-,sizeof(a));}
int locate(ll x)
{
ll l=x%mod;
while(a[l]!=x&&a[l]!=-) l=(l+)%mod;
return l;
}
void insert(ll x,int i)
{
ll l=locate(x);
if(a[l]==-)
{
a[l]=x;
v[l]=i;
}
}
int get(ll x)
{
ll l=locate(x);
return (a[l]==x)?v[l]:-;
}
void clear()
{
memset(a,-,sizeof(a));
}
}s;
void exgcd(ll a,ll b,ll &x,ll &y)
{
if(b==)
{
x=;
y=;
return ;
}
exgcd(b,a%b,x,y);
ll t=x;
x=y;
y=t-a/b*y;
}
int main()
{
ll p,b,n;
while(scanf("%I64d%I64d%I64d",&p,&b,&n)==)
{
s.clear();
ll m=ceil(sqrt(p));
ll t=;
for(int i=;i<m;++i)
{
s.insert(t,i);
t=(t*b)%p;
}
ll d=,ans=-;
ll x,y;
for(int i=;i<m;++i)
{
exgcd(d,p,x,y);
x=((x*n)%p+p)%p;
y=s.get(x);
if(y!=-)
{
ans=i*m+y;
break;
}
d=(d*t)%p;
}
if(ans==-)
printf("no solution\n");
else printf("%I64d\n",ans);
} return ;
}