题解
回忆bsgs算法
给定整数 $a,b,p$ ,其中 $a,p$ 互质,求方程 $a^x\equiv b\ (mod\ p)$ 的最小整数解x
做法:设 $x=i\times m-j,m=\left \lceil \sqrt p \right \rceil,1\le j\le m,1\le i\le m$
方程变为: $a^{im-j}\equiv b\ (mod\ p)$
变形得: $(a^m)^i\equiv b\times a^j\ (mod\ p)$
这时只要把 $(a^m)^i$ 和 $b\times a^j$ 预处理出来丢到哈希表里就做完了
exbsgs算法
而现在的 $a,p$ 不互质了,所以我们要考虑其他的方法,也就是$\text{exbsgs}$
那么我们设 $ g=gcd(a,p)$
根据同余的性质:$ca \equiv cb \pmod m$ 等价于 $a\equiv b \pmod {m/(c,m)}$,特别的当$(c,m)=1$时,等价于 $a \equiv b \pmod m$
方程变为 $\frac{a^x}{g}\equiv \frac{b}{g}\ (mod\ \frac{p}{g})$
无解情况就是 $g\nmid b$ 并且 $b\ne 1$
证明一下:
设 $a’=\frac{a}{g},p’=\frac{p}{g}$,那么 $a=a’g,p=p’g$ ,代入到原方程中变为 $(a’g)^x\equiv b\ (mod\ p’g)$
变形:$a’^xg^x+yp’g=b$,提取公因数g有:$g(a’^xg^{x-1}+yp’)=b$
这样子g就是b的因子,而只有在 $b=1$ 时,$a^0=1$,其余情况若 $g\nmid b$,方程无解
证毕
继续求解exbsgs
那么我们再把上面的式子化一下变为 $a^{x-1}\times\frac{a}{g}\equiv \frac{b}{g}\ (mod\ \frac{p}{g})$
这只是处理了一个a,同余式左边仍有$x-1$个a可能和$\frac{p}{g}$有公因数,举例:若$14^x \equiv 5 \pmod {56} $ 可得:$14^{x-1}\cdot \frac{14}{2} \equiv 5 \pmod {\frac{56}{2}}$,但是$14,\frac{56}{2}$ 之间仍有公因数2。就是这个道理。
而$\frac{p}{g}$ 一定是比 $p$小的,所以可以一直约到$a,\frac{p}{g}$互质,可推出同余式:$a^{x-k} \cdot (\frac{p}{g})^k \equiv \frac{b}{g^k} \pmod {\frac{p}{g^k}}$ 变形得:$a^{x-k} \equiv \frac{b}{g^k \cdot (\frac{p}{g})^k} \pmod {\frac{p}{g^k}}$ ,这个式子可通过一个循环一次一次的算出来。
#include <cstdio>
#include <cmath>
#include <map>
using namespace std;
typedef long long LL;
int a,b,p;
int gcd(int a,int b){
return b==0?a:gcd(b,a%b);
}
void exgcd(int a,int b,LL &x,LL &y){
if(b==0){
x=1,y=0;
return;
}
exgcd(b,a%b,y,x);
y-=a/b*x;
}
LL inv (int a,int p){
LL x,y;
exgcd(a,p,x,y);
return (x%p+p)%p;
}
LL qmi(LL a,LL b,LL p){
LL res=1%p;
while(b){
if(b&1) res=res*a%p;
b>>=1;
a=a*a%p;
}
return res;
}
LL bsgs(int a,int b,int p){
map<int,int> mp;
mp.clear();
int m=ceil(sqrt(p));
LL t=b;
for(int i=1;i<=m;i++){
t=t*a%p;//t*a可能超int,所以t用LL类型
mp[t]=i;
}
a=qmi(a,m,p),t=1;
for(int i=1;i<=m;i++){
t=t*a%p;
if(mp[t]){
return i*m-mp[t];//不可能超过p
}
}
return -1;
}
LL exbsgs(LL a,LL b,LL p){
if(b==1) return 0;
int g=gcd(a,p),k=0,na=1;
while(g>1){
if(b%g) return -1; //如果g不能整除b,无解
k++;b/=g;p/=g;na=na*(a/g)%p;//每循环一次,b,p都被g整除一次,na累乘一个(a/g),注意na每次模的p值是不同的。
if(na==b) return k; //如果相同,答案就提前求出来了
g=gcd(a,p);//这个不能省,用来判断a,p是否互质的
}
LL ans=bsgs(a,b*inv(na,p)%p,p);
if(ans==-1) return -1;
return ans+k;
}
int main(){
scanf("%d%d%d",&a,&p,&b);
while(a||b||p){
a%=p,b%=p;
LL ans=exbsgs(a,b,p);
if(ans==-1) printf("No Solution\n");
else printf("%lld\n",ans);
scanf("%d%d%d",&a,&p,&b);
}
return 0;
}