求x的c(n,m)次方

2025/4/18 23:40:41 来源：https://blog.csdn.net/xuxizhe0104/article/details/147129511 浏览: 次关键词：求x的c(n,m)次方

近期看到一类很有趣的题啊，其最基础的表现形式为求 $x^{\binom{n}{m}}$ mod P的值。

所以我们来拿一道小例题讲讲。

题面：给定 x,n,m，求： $x^{\binom{n}{m}}$ mod 1000003471的值。

首先我们注意到，题目给定的模数1000003471为质数，根据费马小定理， $x^{P-1}$ ≡ $x$ (mod P)。则只需求出 $\binom{n}{m}$ mod (P-1) 即可。

接下来我们将P-1做质因数拆分，得到其质因子{2,3,5,53,677,929}，那么我们可以套用中国剩余定理，将 $\binom{n}{m}$ mod (P-1) ≡ y拆解成数个形似 $\binom{n}{m}$ mod pi ≡ yi的方程，结合中国剩余定理便可得到原始方程。

在求yi的过程中，我们注意到其模数极小，所以无法套用阶乘与逆元的求组合数，我们需要使用到Lucas定理，其针对的便是求出组合数对于小质数取模的结果。

代码：

#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
using namespace std;
const int maxn=1e5+10;
const int mod=1000003471;
inline ll qpow(ll x,ll y,int p){ll r=1;while(y){if(y&1) r=r*x%p;x=x*x%p;y>>=1;}return r;
}
ll inv[maxn],fac[maxn];
inline ll c(int n,int m,int p){if(n<m) return 0;return fac[n]*inv[m]%p*inv[n-m]%p;
}
ll lucas(int n,int m,int p){if(!m) return 1;return lucas(n/p,m/p,p)*c(n%p,m%p,p)%p;
}
inline ll getl(int n,int m,int p){fac[0]=1;for(int i=1;i<p;i++) fac[i]=fac[i-1]*i%p;inv[p-1]=qpow(fac[p-1],p-2,p);for(int i=p-2;~i;i--) inv[i]=inv[i+1]*(i+1)%p;return lucas(n,m,p);
}
ll X,Y,G,lcm;
void exgcd(int a,int b){if(!b){X=1,Y=0,G=a;return;}exgcd(b,a%b);ll t=X;X=Y;Y=t-a/b*X;
}
void getxy(ll a,ll b,int c){exgcd(a,b);X*=c/G;lcm=a/G*b;b/=G;X=(X%b+b)%b;
}
pair<ll,ll> merge(ll a1,ll n1,ll a2,ll n2){getxy(n1,n2,a2-a1);return {(X*n1%lcm+a1)%lcm,lcm};
}
int a[7],b[7]={0,2,3,5,53,677,929},n,m,tot,x;
ll excrt(){pair<ll,ll> cur={0,1};for(int i=1;i<=tot;i++) cur=merge(cur.first,cur.second,a[i],b[i]);return cur.first;
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);tot=6;cin>>x>>n>>m;for(int i=1;i<=tot;i++) a[i]=getl(n,m,b[i]);ll q=excrt();cout<<qpow(x,q,mod)<<endl;return 0;
}

接下来我们再看一道复杂一点的

P2480 [SDOI2010] 古代猪文

同样，简化题面，即为求出 $g^{\sum_{i=1}^{n}[i|n]*\binom{n}{i}}$ mod 999911659。

同样是套用上述方法，拆解出模数质因数为{2,3,4679,35617}。

在求对应yi是对于每个n的因数套用Lucas定理即可，注意特判。

代码：

#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
using namespace std;
const int maxn=1e5+10;
const int mod=999911659;
const int b[]={0,2,3,4679,35617};
inline ll qpow(ll x,int y,int p){x%=mod;ll r=1;while(y){if(y&1) r=r*x%p;x=x*x%p;y>>=1;}return r;
} 
int n,g,m=4;
ll fac[maxn],inv[maxn],a[5];
inline ll c(int n,int m,int p){if(n<m) return 0;return fac[n]*inv[m]%p*inv[n-m]%p;
}
ll lucas(int n,int m,int p){if(!m) return 1;return lucas(n/p,m/p,p)*c(n%p,m%p,p)%p;
}
void so(int p,ll &ans){fac[0]=1;for(int i=1;i<p;i++) fac[i]=fac[i-1]*i%p;inv[p-1]=qpow(fac[p-1],p-2,p);for(int i=p-2;~i;i--) inv[i]=inv[i+1]*(i+1)%p;for(ll i=1;i*i<=n;i++){if(n%i==0){ans+=lucas(n,i,p);if(n/i!=i) ans+=lucas(n,n/i,p);ans%=p;}}
}
ll X,Y,G,lcm;
void exgcd(int a,int b){if(!b){X=1,Y=0,G=a;return;}exgcd(b,a%b);ll t=X;X=Y;Y=t-a/b*Y;lcm=(ll)a/G*b;
}
void getxy(int a,int b,int c){exgcd(a,b);X*=c/G;b/=G;X=(X%b+b)%b;
}
pair<ll,ll> merge(int a1,int n1,int a2,int n2){getxy(n1,n2,a2-a1);return {(X*n1%lcm+a1)%lcm,lcm};
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>g;if(g%mod==0){cout<<0<<endl;return 0;}for(int i=1;i<=m;i++) so(b[i],a[i]);pair<ll,ll> cur={0,1};for(int i=1;i<=m;i++) cur=merge(cur.first,cur.second,a[i],b[i]);cout<<qpow(g,cur.first,mod)<<endl;return 0;
}
/*
2
3
4679
35617
*/