「Bzoj 1951」「Sdoi2010」古代猪文(Lucas + 中国剩余定理合并 + 欧拉定理)

BZOJ 1951
题意：给定$N,G$, 求
$$
G^{\sum_{K|N}C^{\frac NK}_{n}} \mod 999911659
$$

根据欧拉定理推论
$$
a^b \equiv a^{b \mod \varphi(n)} \pmod {n}
$$
以及$999911659$为质数，可以得到
$$
G^{\sum_{K|N}C^{\frac NK}_{n} \mod 999911658} \mod 999911659
$$
那么主要就是求$\sum_{K|N}C^{\frac NK}_{n} \mod 999911658$。
这个可以用 Lucas 来解决，但是模数不一定是质数，我们就要想分解因数再合并。

因为$999911658=2 \times 3 \times 4679 \times 35617$，所以我们可以解出答案模$2,3 ,4679, 35617$意义下的$4$个解，记为$a_i$，那么算完后我们通过以下方程组解得$x$即可求出最终结果：
$$
\begin{cases}
x \equiv a_1 \pmod {2} \\
x \equiv a_2 \pmod {3} \\
x \equiv a_3 \pmod {4679} \\
x \equiv a_4 \pmod {35617}
\end{cases}
$$
显然是中国剩余定理，最终解是在模$2 \times 3 \times 4679 \times 35617=999911658$意义下的，所以符合题意。
然后再快速幂算出最后答案即可。注意特判$999911659|G$的情况。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    LL N, G;
    LL p[10] = {0ll, 2ll, 3ll, 4679ll, 35617ll}, jc[10][50000], a[10], mi[10];
    // p[ith] = MO, jc[ith][n] = n! % p[ith]

    LL ksm(LL a, LL b, LL MO) {
        LL bs = a % MO, ans = 1ll;
        while (b) {
            if (b & 1ll) ans = (ans * bs) % MO;
            bs = (bs * bs) % MO;
            b >>= 1ll;
        }
        return ans;
    }
    void exgcd(LL a, LL b, LL &x, LL &y) {
        if (b == 0ll) {
            x = 1ll, y = 0ll;
            return ;
        }
        exgcd(b, a % b, x, y);
        LL tmp = x;
        x = y, y = tmp - a / b * y;
    }
    LL C(LL n, LL m, LL k) {
        if(n < m) return 0ll; // 不要漏了 
        LL ans = jc[k][n] * ksm(jc[k][m], p[k] - 2ll, p[k]) % p[k];
        return (ans * ksm(jc[k][n - m], p[k] - 2ll, p[k])) % p[k];
    }
    LL lucas(LL n, LL m, LL k) {
        if (n < m) return 0ll; // 不要漏了 
        if (m == 0ll) return 1ll;
        return C(n % p[k], m % p[k], k) * lucas(n / p[k], m / p[k], k) % p[k];
    }

    void clean() {
        ms(a, 0ll);
    }
    int solve() {
        clean();
        cin >> N >> G;
        if (G % 999911659ll == 0ll) return printf("0\n"), 0; 
        for (LL j = 1ll; j <= 4ll; ++j) {
            jc[j][0] = 1ll;
            for (LL i = 1ll; i <= p[j]; ++i) jc[j][i] = (jc[j][i - 1] * i) % p[j];
        }
        LL test = lucas(15015, 5005, 1);
        for (LL j = 1ll; j <= 4ll; ++j) {
            for (LL i = 1ll; i * i <= N; ++i) {
                if (N % i == 0) {
                    a[j] = (a[j] + lucas(N, i, j)) % p[j];    
                    if (N / i != i) a[j] = (a[j] + lucas(N, N / i, j)) % p[j];    
                }
            }
        }
        for (LL i = 1ll; i <= 4ll; ++i) mi[i] = p[i];
        LL M = 999911658ll, ans = 0ll;
        for (LL i = 1ll; i <= 4ll; ++i) {
            LL Mi = M / mi[i], x, y; exgcd(Mi, mi[i], x, y);
            ans = (ans + (a[i] * Mi % M) * x % M) % M;
        }
        cout << ksm(G, (ans + M) % M, 999911659ll);
        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}