链接

　　https://www.luogu.org/problem/show?pid=2480

题解

　　大型数论综合题。出题人太神辣！ 　　回顾起来，这道题的套路真的是登峰造极。 　　概括一下题目，就是让你求 　　

x=∑d|NCdNans=Gx mod 999911659 　　首先注意到一个问题，x可能会很大很大，而答案中它竟然做指数！高精？明显会炸。这里很神地使用了费马小定理 ap−1 mod p=1 ，于是我们将指数对 p−1 取膜 　　 ans=Gx mod (999911659−1) 　　现在问题转成，求 x mod 999911658 　　 C 计算里有除法，就要用逆元，明显这个合数必须被拆成素数 　　999911659=2×3×4679×35617 　　现在就可以用 laces 求组合数了。 　　约数可以根号找，总的时间复杂度 O(N−−√logNp) 　　最后注意一点，如果G=999911659，那么费马小定理将不成立，要特判(第20个测试点)。

代码

//卢卡斯定理+费马小定理+中国剩余定理 #include <cstdio> #include <algorithm> #define ll long long using namespace std; ll a[5], m[5], N, G, frac[1000000]; inline void exgcd(ll a, ll b, ll &x, ll &y) { if(!b){x=1,y=0;return;} ll xx, yy; exgcd(b,a%b,xx,yy); x=yy, y=xx-a/b*yy; } inline ll inv(ll a, ll p) { ll x, y; exgcd(a,p,x,y); return (x+p)%p; } inline ll C(ll n, ll m, ll p) { if(m>n)return 0; return frac[n]*inv(frac[n-m]*frac[m]%p,p)%p; } inline ll lacus(ll n, ll m, ll p) { if(n==0)return 1; return lacus(n/p,m/p,p)*C(n%p,m%p,p)%p; } inline ll calc(ll p) { ll x=0, i; frac[0]=1; for(i=1;i<=p;i++)frac[i]=frac[i-1]*i%p; for(i=1;i<=N;i=N/(N/i)+1) { if(N%(N/i))continue; x=(x+lacus(N,N/i,p))%p; } return x; } inline ll CRT(ll *a, ll *m, ll n) { ll M=1, i, ans=0; for(i=1;i<=n;i++)M*=m[i]; for(i=1;i<=n;i++)ans=(ans+a[i]*(M/m[i])%M*inv(M/m[i],m[i])%M)%M; return ans; } inline ll pow(ll a, ll b, ll p) { ll t, ans; for(t=a,ans=1;b;b>>=1,t=t*t%p)if(b&1)ans=ans*t%p; return ans; } int main() { ll i, x; scanf("%lld%lld",&N,&G); if(G==999911659) { if(N==1)printf("1\n"); else printf("0\n"); return 0; } m[1]=2, m[2]=3, m[3]=4679, m[4]=35617; for(i=1;i<=4;i++)a[i]=calc(m[i]); x=CRT(a,m,4); printf("%lld",pow(G