思路
很容易得出我们要简化$G^{\sum_{k|n} C_{n}^{k}}≡ans (modP)$的指数
我们阔以首先用欧拉定理(费马小定理)$a^{p-1}≡1(mod P)$优化一波
=>指数膜(p-1)
在应再用卢卡斯定理
很明显999911658不是个质数
但我们可以把它转化为2x3x4679x35617分别卢卡斯
在运用中国剩余定理求最小正整数解x
最后再来个快速幂
C++ 代码
#include<bits/stdc++.h>
#define re return
#define ll long long
#define inc(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
template<typename T>inline void rd(T&x)
{
char c;bool f=0;
while((c=getchar())<'0'||c>'9')if(c=='-')f=1;
x=c^48;
while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);
if(f)x=-x;
}
const int maxn=36000;
ll jc[maxn],inv[maxn],jcinv[maxn],N,G;
ll C(int n,int m,int mod)//组合数
{
if(m>n)re 0;
re jc[n]*jcinv[n-m]%mod*jcinv[m]%mod;
}
ll LUCAS(int n,int m,int mod)//卢卡斯定理
{
if(!m)re 1;
re C(n%mod,m%mod,mod)*LUCAS(n/mod,m/mod,mod)%mod;
}
inline void Get_math(int mod)
{
//得到当前模数下的阶乘,阶乘逆元
jcinv[0]=jcinv[1]=inv[1]=jc[1]=jc[0]=1;
inc(i,2,mod)
{
inv[i]=(mod-mod/i)*inv[mod%i]%mod;
jcinv[i]=jcinv[i-1]*inv[i]%mod;
jc[i]=jc[i-1]*i%mod;
}
}
inline ll Get_crt(int mod)
{
ll sum=0;
Get_math(mod);
inc(i,1,sqrt(N))
if(N%i==0)//寻找整除N的K
{
sum=(sum+LUCAS(N,i,mod))%mod;
if(i*i!=N)//防止重复
sum=(sum+LUCAS(N,N/i,mod))%mod;
}
re sum;
}
inline ll pow(ll a,ll x,ll mod)
{
if(!a)re 0;
ll ret=1;
while(x)
{
if(x&1)ret=ret*a%mod;
a=a*a%mod;
x>>=1;
}
re ret;
}
int main()
{
freopen("in.txt","r",stdin);
ll a1,a2,a3,a4,x,M=999911658;
ll inv1,inv2,inv3,inv4;
rd(N),rd(G);
//得到中国剩余定理的X=(请当做同余)A(mod p)中的A
a1=Get_crt(2);
a2=Get_crt(3);
a3=Get_crt(4679);
a4=Get_crt(35617);
//剩余定理求解
inv1=pow(M/2,2-1,M)*a1;
//Mi*(Mi^(p-2))*ai前面可以合并
//并对M取模得到最小正整数解
inv2=pow(M/3,3-1,M)*a2;
inv3=pow(M/4679,4679-1,M)*a3;
inv4=pow(M/35617,35617-1,M)*a4;
printf("%lld",pow(G%(M+1),(inv1+inv2+inv3+inv4)%M,M+1));
re 0;
}
为啥求逆元是35617-1,不应该减2吗
你求了逆元(35671-2)之后,根据中国剩余定理Xi=AixMix(Mi的逆元=Mi^(35671-2))=AixMi^(35671-1)
我就是懒,写到一起了
呃呃呃 我傻了