1.BSGS
求解如关于$x$的方程$A^x≡B \mod\ p$ 的最小整数解。$(A,p互质,p为质数)$
不难发现$x<=p$ 因为会出现循环。
靠虑将$x$分解为$i\times sqrt(p)-j$ 。
则原式化为$A^{i\times \lceil sqrt(p)\rceil}\times A^{-j}≡B \mod\ p$
对$A^{-j}$求逆元得$A^{i\times \lceil sqrt(p)\rceil}≡B\times A^j \mod\ p$
因为可以求一个同余方程$A^{-j}\times inv_{A^{-j}}≡1\ mod\ p$
显而易见$inv_{A^{-j}}$即为$A^j$ ,其实有点像移项,可惜$p$不与$A$互质移不过来,可能导致左边$mod\ p$后为$0$
然后可知在$mod\ p$的意义下左右两式相等。
所以就可以用$map$把左右的值映射成它的指数,先做右边($j$从$0$枚举到$\lceil sqrt(p)\rceil$),并把每次的$j$映射到$map$以$B\times A^j$为下标的空间中。然后做左边($i$从$1$枚举到$ \lceil sqrt(p)\rceil$),每次查表搞一搞,第一次遇到相同的值就可以拿现在的$i\times \lceil sqrt(p)\rceil$与表中的$j$相减即为最小值,因为此时$i\times \lceil sqrt(p)\rceil$最小,$j$最大。
理论时间复杂度为$O(sqrt(p))$,但由于用了$map$所以多了红黑树查值的复杂度,所以多了个$log$。
代码
#include<bits/stdc++.h>
using namespace std;
long long b,p,a;
void Read(long long &x)
{
long long f=1;x=0;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
x*=f;
}
long long KSM(long long base,long long index,long long p)
{
long long Res=1;
while (index)
{
if (index%2==1) Res*=base,Res%=p;
base*=base;
base%=p;
index/=2;
}
return Res%p;
}
long long BSGS(long long a,long long b,long long p)
{
map <long long,long long> m;
long long X=(long long)ceil(sqrt(p));
m[b]=0;
long long Ans_=b;
for (int i=1;i<=X;i++) Ans_*=a,Ans_%=p,m[Ans_]=i;
long long Ans__=KSM(a,X,p);
long long Ans___=1,Ans=-1;
for (int i=1;i<=X;i++)
{
Ans___*=Ans__,Ans___%=p;
if (m.count(Ans___)) {Ans=i*X-m[Ans___];break;}
}
return Ans;
}
int main()
{
Read(p),Read(a),Read(b);
long long answer=BSGS(a,b,p);
if (answer==-1) cout<<"no solution"<<endl;
else cout<<answer<<endl;
return 0;
}
2.exBSGS
若$A,p$不互质,那普通的$BSGS$就难以胜任了,所以需要使用$exBSGS$
其实也很简单,假设$t=gcd(A,p)$,则可推出$A^{x-1}\times \frac{A}{t}≡\frac{B}{t} \mod p$
若$t\nmid B$,则只有$B=1$时有$x=0$的最小解
若$t \mid b $,则当$t=1$时用$BSGS$,求解即可。
反复执行,直至$A,p$互质。
最后,若此过程需要反复进行$k$次,则答案为$BSGS$的解$x+k$。
代码
#include<bits/stdc++.h>
using namespace std;
long long b,p,a;
void Read(long long &x)
{
long long f=1;x=0;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
x*=f;
}
long long gcd(long long a,long long b)
{
if (b==0) return a;
return gcd(b,a%b);
}
long long KSM(long long base,long long index,long long p)
{
long long Res=1;
while (index)
{
if (index%2==1) Res*=base,Res%=p;
base*=base;
base%=p;
index/=2;
}
return Res%p;
}
void ex_gcd(long long a,long long b,long long &d,long long &x,long long &y) {
if (b==0) x=1,y=0,d=a;
else
{
ex_gcd(b,a%b,d,x,y);
long long tmp=x;x=y;y=tmp-a/b*y;
}
}
long long inv(long long a,long long b)
{
long long x,y,d;
ex_gcd(a,b,d,x,y);
return (x%b+b)%b;
}
long long BSGS(long long a,long long b,long long p)
{
map <long long,long long> m;
long long X=(long long)ceil(sqrt(p));
m[b]=0;
long long Ans_=b;
for (int i=1;i<=X;i++) Ans_*=a,Ans_%=p,m[Ans_]=i;
long long Ans__=KSM(a,X,p);
long long Ans___=1,Ans=-1;
for (int i=1;i<=X;i++)
{
Ans___*=Ans__,Ans___%=p;
if (m.count(Ans___)) {Ans=i*X-m[Ans___];break;}
}
return Ans;
}
long long exBSGS(long long a,long long b,long long p)
{
if (b==1||p==1)return 0;
long long g=gcd(a,p),k=0,na=1;
while (g!=1)
{
if (b%g!=0)return -1;
k++;b/=g;p/=g;na=na*(a/g)%p;
if (na==b)return k;
g=gcd(a,p);
}
long long f=BSGS(a%p,b*inv(na,p)%p,p);
if (f==-1)return -1;
return f+k;
}
int main()
{
while (1)
{
Read(a),Read(p),Read(b);
if (p==0||a==0||b==0) break;
long long answer=exBSGS(a,b,p);
if (answer==-1) cout<<"No Solution"<<endl;
else cout<<answer<<endl;
}
return 0;
}
评论