最近在学习数论，然而发现之前学的baby step giant step又忘了，于是去翻了翻以前的代码，又复习了一下。
觉得总是忘记是因为没有彻底理解啊。
注意baby step giant step只能用在b和p互质的情况下，因为只有b和p互质的情况下，b才有mod p下的逆元。（下面要用到逆元）
当b和p不互质，就要处理一下。现在就正在做这么一题，方法以后再写。
求a^(-m)就用到了求逆元了，那么如何求逆元呢？我学了两种方法：
·1：欧拉定理：当a和n互质，a^φ ( n) ≡ 1(mod n)。【φ ( n) 是小于等于n的与n互质的数的个数】
·2：拓展欧几里德：设a在mod n下的逆元是x，则满足：ax ≡ 1(mod n)
即ax+ny=1。（a和n是常数，x和y是未知数，用拓展欧几里德求解即可）
注：只有当a和n互质，a才有mod n下的逆元。
代码如下：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define LL long long
#define Maxn 1000010 struct node
{
int idx;
LL val;
}baby[Maxn]; bool cmp(node x,node y) {return x.val!=y.val ? x.val<y.val : x.idx<y.idx;} int binsearch(int cnt,LL tmp)
{
int head=,tail=cnt;
while(head<=tail)
{
int mid=(head+tail)>>;
if(baby[mid].val==tmp) return baby[mid].idx;
if(baby[mid].val<tmp) head=mid+;
else tail=mid-;
}
return -;
} LL powmod(LL a,LL b,LL mod)
{
LL ret=;
a%=mod;
while(b)
{
if(b&) ret=(ret*a)%mod;
a=(a*a)%mod;
b>>=;
}
return ret;
} int main()
{
LL p,b,n;
while(scanf("%lld%lld%lld",&p,&b,&n)!=EOF)
{
int m=(int)ceil(sqrt((double)(p-))),cnt=;
baby[].idx=,baby[].val=;
for(int i=;i<m;i++)
baby[i].idx=i,baby[i].val=(baby[i-].val*b)%p;
sort(baby,baby+m,cmp);
for(int i=;i<m;i++)
if(baby[i].val!=baby[cnt].val) baby[++cnt]=baby[i];
LL bm=powmod(powmod(b,p-,p),m,p);
//printf("bm = %lld\n",bm);
int ans=-;
LL tmp=n;
for(int i=;i<m;i++)
{
int pos=binsearch(cnt,tmp);
if(pos!=-)
{
ans=i*m+pos;
break;
}
tmp=(tmp*bm)%p;
}
if(ans==-) printf("no solution\n");
else printf("%d\n",ans);
}
return ;
}
poj2417
2016-02-03 09:50:33