给定整数a,b,p,其中a,p互质(或者说p是质数),求一个非负整数x,使得(a^x≡b(mod p))
设(x=i*t-j),其中(t=sqrt q)(向上取整),(0<=j<=t-1),则方程变为(a^{i*t-j}≡b(mod p)),整理一下式子得((a^t)^i≡b*a^j(mod p))
对于所有的(j(0<=j<=t-1)),我们可以计算出(b*a^jmod p)的值,并插入哈希表或者map中.
然后枚举i的所有取值((0<=i<=t)),同样可以计算出((a^t)^imod p)的值,然后在hash表中查找是否存在对应的j,如果有则(x=i*t-j)记录答案即可.
时间复杂度为(O(sqrt p))
代码实现:(我粗略地分为两种:第一种直接按照上述分析来的,很好理解,时间复杂度实际上是(O(sqrt p*log),log)是因为快速幂;第二种就可以不用快速幂直接累乘上去,时间复杂度才是真正的(O(sqrt p)))
LL BSGS(LL a,LL b,LL p){
if(a%p==0)return -1;//特判
map<LL,LL>hash;hash.clear();
//直接开个map存值,多组数据时记得清空
b%=p;
LL t=(int)sqrt(p)+1;
//计算根号p向上取整的值,用ceil也可以
for(int j=0;j<t;j++){
LL val=1LL*b*ksm(a,j,p)%p;
//这里经常要用到龟速乘
hash[val]=j;
}
//计算出b*a^j mod p的值,并存入map中
a=ksm(a,t,p);
//先算出a^t的值
if(a==0)return b==0?-1:1;//特判一下
for(int i=0;i<=t;i++){
LL val=ksm(a,i,p);
//即(a^t)^i
int j=hash.find(val)==hash.end()?-1:hash[val];
//到map中去找是否有对应的值
if(j>=0&&i*t-j>=0)return i*t-j;
//如果有就直接输出答案x=i*t-j
}
return -1;
//一直没找到则无解
}
LL BSGS(LL a,LL b,LL p){
if(a%p==0)return -1;
map<LL,LL>hash;hash.clear();
LL t=ceil(sqrt(p)),cnt=1,val=b%p;
hash[val]=0;//b*(a^j) mod p,当j=0时的情况
for(int j=1;j<=t;j++){
cnt=(cnt*a)%p;//计算a^t,方便下面用
val=(val*a)%p;//计算b*(a^j)
hash[val]=j;
}
val=1;
for(int i=1;i<=t;++i){
val=(val*cnt)%p;
//此时cnt=a^t,这里相当于计算(a^t)^i
if(hash[val]){
LL ans=(t*i-hash[val]+p)%p;
return ans;
}
}
return -1;
}
模板题,没有任何改动.不放代码了.
题意:给定整数(K)和质数(m)，求最小的正整数(N)，使得 $ 11cdots1$（N个1） (equiv K pmod m)
分析:x个1可以表示为((10^x-1)/9),所以本题实际上是求最小正整数x,使得(10^xequiv9*k+1(mod m)),就是BSGS的板子题了.
但是本题数据毒瘤,最后两个点卡到怀疑人生,直接乘爆long long,写龟速乘真的就龟速了,用__int128还必须要写快读快写,原因好像是我的板子里的map太慢.
所以我学会了链式前向星hash和神仙O(1)快速乘.
#include<bits/stdc++.h>
#define LB long double
#define LL long long
using namespace std;
struct Hash{
LL p,x,y;
}b[376637];
LL tot,head[376637];
inline LL read(){
LL s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
return s*w;
}
inline LL ksc(LL x,LL y,LL p){
return (x*y-(LL)((LB)x/p*y)*p+p)%p;
}
inline void hash(LL x,LL y){
b[++tot].x=x;b[tot].y=y;y%=376637;
b[tot].p=head[y];head[y]=tot;
}
inline LL BSGS(LL x,LL y,LL p){
LL z=sqrt(p)+1,sx=1,sy=1;
for(int i=0;i<z;i++){
sx=ksc(sx,x,p);
hash(i,ksc(sx,y,p));
}
sy=sx;
for(int i=1;i<=z;++i,sy=ksc(sy,sx,p)){
for(int j=head[sy%376637];j;j=b[j].p)
if(sy==b[j].y)return (LL)i*z-b[j].x;
}
}
int main(){
LL k=read(),m=read();k=(k*9+1)%m;
printf("%lld
",BSGS(10,k,m));
return 0;
}
依旧模板题,但需要特判几个地方
if(a%p==0){
printf("Couldn't Produce!
");
continue;
}
if(b==1){
puts("0");
continue;
}
如果掌握了扩展欧几里得和BSGS,这里有道模板题