题解：P12694 BZOJ2219 数论之神

Purslane · 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)}。这个解的个数为：

否则，考虑 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 中能用到的同余数论的板子几乎在这里凑齐了：

2. 质因数分解算法，用来将 n 进行质因数分解，计算 \varphi，以及进行试除。
3. 计算阶（使用试除法）。
4. 快速幂。
5. 计算原根。（有结论（超出初等数论范畴）：n 如果存在原根，则一定存在一个 O(n^{0.25+\epsilon}) 范围内的原根。所以可以直接枚举）

大家可以做这道题来进行 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;
}