为啥这种写法会 WA：

ll ExBSGS(ll a,ll b,ll p){//a^x=b(mod p)
	if(p==1||b==1) return 0;
	int k=0;ll d=1;
	while(__gcd(a,p/d)>1){++k,d*=__gcd(a,p/d);}
	if(b%d!=0) return -1;
	for(ll cur=1,x=0;x<=k;++x,cur=cur*a%p){
		if(cur==b) return x;
	}
	if(!k) return BSGS(a,b,p);
	ll res=BSGS(a,b/d*Inv(a/d*Pow(a,k-1,p/d)%(p/d),p/d)%(p/d),p/d);
	if(~res) return res+k;
	return -1;
}

而这种写法就能过：

ll ExBSGS(ll a,ll b,ll p){//a^x=b(mod p)
	if(p==1||b==1) return 0;
	int k=0;ll g,d=1;
	while((g=__gcd(a,p))>1){
		if(b%g) return -1;
		b/=g,p/=g,d=d*(a/g)%p,++k;
		if(b==d) return k;
	}
	ll res=BSGS(a,b*Inv(d,p)%p,p);
	if(~res) return res+k;
	return -1;
}

完整代码：https://www.luogu.com.cn/paste/bjy0tbnz