自动搬运

查看原文

来自洛谷，原作者为

	Purslane AFO

搬运于2025-08-24 23:17:29，当前版本为作者最后更新于2025-06-04 16:58:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Solution

也就是求 $x^a \equiv b \pmod n$ 的解的个数，其中 $n$ 是奇数。

---

先考虑这样一个问题：对于奇质数 $p$，求解 $x^a \equiv b \pmod {p^k}$。如果会做这个，就可以把 $n$ 进行质因数分解，然后把解数乘起来即可。

根据著名定理（经常学 MO 的同学都知道，这个其实并不好证，需要用到一大串引理），$p^k$ 必存在原根 $g$。

当 $\gcd(b,p)=1$ 的时候，显然 $\gcd(x,p)=1$，设 $x \equiv g^s$，且 $b \equiv g^t$，则 $sa \equiv t \pmod {\varphi(p^k)}$。这个解的个数为：

$$\left\{ \begin{matrix} \gcd(a,\varphi(p^k))&, \text{if } \gcd(a,\varphi(p^k)) \mid t \\ 0 &,\text{otherwise} \end{matrix} \right. $$

否则，考虑 $v_p(b)$（表示 $b$ 中质因子的个数），则 $b=p^{v_p(b)}B$。

当 $k \le v_p(b)$ 的时候，保证 $a v_p(x) \ge k$ 即可；否则，应当由 $a \mid v_p(b)$，得到 $v_p(x) = \frac{v_p(b)}{a}=s$。这样设 $x = p^s \cdot x'$，有 $p^{v_p(b)} (x')^a \equiv p^{v_p(b)} B \pmod {p^k}$。则 $(x')^a \equiv B \pmod {p^{k-v_p(b)}}$。不过这样解出来的 $x' < p^{k-v_p(b)}$，而实际上 $x' < p^{k-s}$，所以你的解数还得乘上 $p^{v_p(b)-s}$。

---

然后是实现问题。NOI 中能用到的同余数论的板子几乎在这里凑齐了：

1. $\rm BSGS$，用来求解离散对数。
2. 质因数分解算法，用来将 $n$ 进行质因数分解，计算 $\varphi$，以及进行试除。
3. 计算阶（使用试除法）。
4. 快速幂。
5. 计算原根。（有结论（超出初等数论范畴）：$n$ 如果存在原根，则一定存在一个 $O(n^{0.25+\epsilon})$ 范围内的原根。所以可以直接枚举）
6. $\gcd$ 的计算，以及 $\rm ExGCD$ 算法。
7. $\rm ExCRT$（如果你需要求出一个解。不过本题不需要）

大家可以做这道题来进行 NOI 常见数论模板的复习。一个参考代码：

#include<bits/stdc++.h>
#define int long long 
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
int T,a,b,k;
vector<pair<int,int>> fractor_divide(int n) {
	vector<pair<int,int>> ans;
	ffor(i,2,n/i) if(n%i==0) {
		int cnt=0;
		while(n%i==0) cnt++,n/=i;	
		ans.push_back({i,cnt});
	}
	if(n!=1) ans.push_back({n,1});
	return ans;
}
int calc_phi(int n) {
	int ans=n;	
	ffor(i,2,n/i) if(n%i==0) {
		int cnt=0;
		while(n%i==0) cnt++,n/=i;
		ans=ans/i*(i-1);
	}
	if(n!=1) ans=ans/n*(n-1);
	return ans;
}
pair<int,int> exgcd(int a,int b) {
	if(!b) return {1,0};
	auto pr=exgcd(b,a%b);
	return {pr.second,pr.first-a/b*pr.second};
}
int calc_inv(int x,int mod) {
	return (exgcd(x,mod).first%mod+mod)%mod;
}
int qpow(int base,int p,int mod) {
	int ans=1;
	while(p) {
		if(p&1) ans=ans*base%mod;
		base=base*base%mod,p>>=1;	
	}
	return ans;
}
int check(int v,int n,vector<int>& p,int phi) {
	for(auto id:p) if(qpow(v,phi/id,n)==1) return 0;
	return 1;
}
int get_root(int n) {
	int phi=calc_phi(n);
	auto vc=fractor_divide(phi);
	vector<int> p;
	for(auto pr:vc) p.push_back(pr.first);
	ffor(i,2,n) if(check(i,n,p,phi)) return i;
}
int get_log(int g,int v,int n) {
	unordered_map<int,int> mp;
	int tmp=1,B=sqrt(n);
	ffor(i,0,B-1) {
		if(tmp==v) return i;
		mp[tmp]=i,tmp=tmp*g%n;	
	}
	int inv=calc_inv(tmp,n);
	tmp=1;
	ffor(i,0,B+1) {
		if(mp.count(v*tmp%n)) return i*B+mp[v*tmp%n];
		tmp=tmp*inv%n;	
	}
	return -1;
}
int calc(int a,int b,int p,int k) {
	int n=1;
	ffor(i,1,k) n=n*p;
	b%=n;
	if(b%n==0) {
		int ans=1,tmp=n;
		ffor(j,1,k-1) {
			tmp/=p;
			if(a*j>=k) ans+=tmp/p*(p-1);
		}
		return ans;
	}
	if(b%p==0) {
		int vp=0,B=b;
		while(B%p==0) vp++,B/=p;
		if(vp%a) return 0;
		int mul=1;
		ffor(i,1,vp-vp/a) mul=mul*p;
		return calc(a,B,p,k-vp)*mul;	
	}
	int g=get_root(n),phi=calc_phi(n);
	int t=get_log(g,b,n);
	if(t%__gcd(a,phi)) return 0;
	return __gcd(a,phi);
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--) {
		cin>>a>>b>>k;
		int ans=1;
		auto vc=fractor_divide(2*k+1);
		for(auto pr:vc) ans=ans*calc(a,b,pr.first,pr.second);
		cout<<ans<<'\n';
	}
	return 0;
}