Fork me on GitHub

扩展BSGS

发表于 | | 阅读次数:
字数统计: 308

先看这样一个性质:

若A≡B(mod P)

假设d=gcd(A,P)，且B%d=0

则 $\frac{A}{d}$ ≡$\frac{B}{d}$(mod $\frac{P}{d}$)

所以只要B%d==0,就能一直化简直到d=gcd(A,P)=1

我们再来$a^x$ ≡b(mod P)

如果也能这样化简的话就能直接用BSGS做了

显然如果化简过程中B%d!=0，那么就无解

于是原方程可以写为$A^{x-cnt}​$ * $\frac{A^{cnt}}{S}​$≡$\frac{B}{S}​$(mod $\frac{P}{S}​$)

( S=d1* d2* d3 * … *dcnt)

换元，$A^{‘}$ ≡ $\frac{A^{x-cnt}}{S}$，$B^{‘}$≡$\frac{B}{S}$ ，$P^{‘}$≡$\frac{P}{S}$

此时 $P^{‘}$ 为质数，就用BSGS处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
ll exbsgs(ll A,ll B,ll P){
	A%=P,B%=P;
	if(B==1)return 0;
	if(!A&&!B)return 1;
	if(!A)return -1;
	ll cnt=0;
	ll K=1;
	ll d;
	while((d=gcd(A,P))!=1){
		if(B%d)return -1;
		cnt++;
		B/=d,P/=d;
		K=K*(A/d)%P;
		if(B==K)return cnt;
	}
	ll M=ceil(sqrt(P));
	Hash.clear();
	ll val=1;
	for(ll i=0;i<M;++i){
		Hash[val*B%P]=i;
		val=val*A%P;
	}
	for(ll i=M;;i+=M){
		K=K*val%P;
		if(Hash.count(K))return i-Hash[K]+cnt;
		if(i>P)break;
	}
	return -1;
}

PSS：用map存可能会TLE（？？？）所以最好用哈希表

0%
``` ```