题目传送门(BZOJ)

题解 :

题意即求 :

P = \sum\limits_{k|N}C(N, k)\;\;\;\;\;G^P\mod 999911659

\because G^P\equiv G^{P\%\varphi(mod)}

mod是个质数, 所以\varphi(mod) = 999911658

所以关键变成了求\sum\limits_{k|N}C(N,k)\mod 999911658

发现如果能用lucas的话, 由于约数是不到\sqrt N级别的(在10^9范围内, 最多的一个不超过2000)

那么我们O(\sqrt N)分解约数, 再2000\times \log N lucas(由于约数不可能都到N级别, 实际会小).

然后999911658并不是一个质数, 999911658 = 2\times 3\times 4679\times 35617

我们对于这四个质因数分别求解, 再用CRT合并一下就可以了, 当然也可以同余方程求解

对于每个质因数pritmp=999911658\div pri,答案等于

(\sum\limits_{k|N}C(N,k)\mod pri) \times tmp\%999911658\times inv(tmp)

我们把每个质因数的答案加起来就是要求的P

代码 :

#include <bits/stdc++.h>using namespace std;#define ll long longconst ll p1 = 999911659, p2 = p1-1;int num[4] = {2, 3, 4679, 35617};int n, g;ll fac[40000], sum[4];inline ll quickpow(ll x, ll y, ll p) { ll res = 1; for(; y; y >>= 1, x = x*x%p) if(y&1) res = res*x%p; return res;}ll C(ll n, ll m, ll p) { if(n<m)return 0; return n<p&&m<p?fac[n]*quickpow(fac[n-m]*fac[m]%p, p-2, p)%p: C(n/p, m/p, p)%p*C(n%p, m%p, p)%p;}inline ll crt() { ll ans=0; for(int i = 0; i < 4; i ++ ) { ll tmp = p2/num[i]; ans = (ans+1LL*sum[i]*tmp%p2*quickpow(tmp, num[i]-2, num[i])%p2)%p2; } return ans;}int main() { scanf("%d%d", &n, &g); if(g%p1 == 0) return puts("0"), 0; for(int i = 0; i < 4; i ++ ) { fac[0]=1; for(int j = 1; j <= num[i]; j ++ ) fac[j] = fac[j-1]*j%num[i]; for(int k = 1; k*k <= n; k ++ ) { if(n%k != 0)continue; sum[i] = (sum[i]+C(n, k, num[i]))%num[i]; if(n/k == k)continue; sum[i] = (sum[i]+C(n, n/k, num[i]))%num[i]; } } ll sum = quickpow(g, crt(), p1); printf("%lld\n", sum);}