转：

数论之神

数论之神

求解方程(x^Aequiv B(bmod 2k+1))的解的个数

首先由于模数不是质数，所以我们先考虑拆分成质数的幂次形式，然后分别求解，可以发现根据CRT的性质，对于两两互质的模数，我们构成的剩余系和原来的数形成双射，所以所有解得个数等于每个方程解的个数的乘积。

问题转化为(x^Aequiv B(bmod p^a))然后考虑分类讨论。

第一种情况，当(p^a|B)时，问题等价于(x^Aequiv 0(bmod p^a))那么将x表示成p的形式(x=p^kb),(p^{kA}b^Aequiv0(bmod p^a))

那么必然有(kAge a)所以$kge lceil frac{a}{A} rceil $

那么解的个数就应该是(p^{a-lceil frac{a}{A} rceil})

第二种情况，当((p^a,B)=1)，将方程转化为(Aind(x)equiv ind(B)(bmodvarphi(p^a)))

然后利用BSGS可以求出(ind(B)),那么方程变成(axequiv b(bmod p))

原方程解的个数对应上面方程解的个数

如果(bbmodgcd(a,p)ne 0)则无解，否则解的个数为(gcd(a,p))，这是因为我们考虑(exgcd)的周期为(gcd(a,p))，所以一共有(frac{p}{gcd(a,p)})个点，每个点恰好被经过(frac{p}{frac{p}{gcd(a,p)}}=gcd(a,p))次。

第三种情况，当((p^a,B)ne1),将(B=p^{cnt}b)原方程变为(x^Aequiv p^{cnt}b(bmod p^a))

如果(cnt bmod Ane0)此方程无解

否则把方程转化为

[(frac{x}{p^{frac{cnt}{A}}})^Aequiv b(bmod p^{a-cnt}) ]

此时((p^{a-cnt},b)=1),方程转化为第二种情况。

但是原式中x的取值范围是([0,p^a])，那么(frac{x}{p^{frac{cnt}{A}}})的取值范围就是([0,p^{a-frac{cnt}{A}}])

但是在最后这个式子里(frac{x}{p^{frac{cnt}{A}}})的取值范围是([0,p^{a-cnt}))

所以最后需要在结果上乘(frac{p^{a-frac{cnt}{A}}}{p^{a-cnt}}=p^{cnt-frac{cnt}{A}})

转：

数论之神