近期看到一类很有趣的题啊，其最基础的表现形式为求 mod P的值。
所以我们来拿一道小例题讲讲。
题面：给定 x,n,m，求：
mod 1000003471的值。
首先我们注意到，题目给定的模数1000003471为质数，根据费马小定理，≡
(mod P)。则只需求出
mod (P-1) 即可。
接下来我们将P-1做质因数拆分，得到其质因子{2,3,5,53,677,929}，那么我们可以套用中国剩余定理，将 mod (P-1) ≡ y拆解成数个形似
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] 古代猪文
同样，简化题面，即为求出 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
*/