P2480 [SDOI2010]古代猪文

题目大意：

给定 G,n，1\le G,n\le 10^9，求：

G^{\sum_{k|n}\binom{n}{k}}\bmod 999911659

分析：

由于 P=999911659 是质数，所以当 G\bmod P=0 时，答案为 0；否则：

ans=G^{\sum_{k|n}\binom{n}{k}\bmod 999911658}\bmod 999911659

考虑如何计算：

\sum_{k|n}\binom{n}{k}\bmod 999911658

分解质因数，999911658=2\times 3\times4679\times 35617。我们可以分别求出：

\begin{cases}
a_1=\sum_{k|n}\binom{n}{k}\bmod 2\cr a_2=\sum_{k|n}\binom{n}{k}\bmod 3\cr a_3=\sum_{k|n}\binom{n}{k}\bmod 4679\cr a_4=\sum_{k|n}\binom{n}{k}\bmod 35617\cr
\end{cases}

然后利用 CRT 合并方程组：

\begin{cases}
x\equiv a_1\pmod 2\cr x\equiv a_2\pmod 3\cr x\equiv a_3\pmod {4679}\cr x\equiv a_4\pmod {35617}\cr
\end{cases}

我们可以用 O(\sqrt n) 的复杂度筛出其全部的因子；对于组合数的计算，我们可以使用卢卡斯定理。

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int P = 999911659;

ll Mo[5] = {0, 2, 3, 4679, 35617}, x[5];
int n, g;
vector<int> d;

int ksm(int a, ll b, int P) {
    int ret = 1;
    for (; b; b >>= 1, a = 1LL * a * a % P) {
        if (b & 1) {
            ret = 1LL * ret * a % P;
        }
    }
    return ret;
}
void exgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1; y = 0;
    }
    else {
        exgcd(b, a % b, y , x);
        y -= a / b * x;
    }
}
ll ni(ll a, ll p) {
    ll x = 0, y = 0;
    exgcd(a, p, x, y);
    return (x % p + p) % p;
}

int C(int n, int m, int P) {
    if(n < m) return 0;
    int ans = 1, tmp = 1;
    for(int i = n; i >= n - m + 1; i--) ans = 1LL * ans * i % P;
    for(int i = m; i >= 1; i--) tmp = 1LL * tmp * i % P;
    return ni(tmp, P) * ans % P;
}
int Lucas(int n, int m, int p) {
    if (m == 0) return 1;
    return 1LL * Lucas(n / p, m / p, p) * C(n % p, m % p, p) % p;
}

ll crt(ll *a, ll *b, int k) {
    ll ans = 0, lcm = 1, x, y;
    for(int i = 1; i <= k; i++) lcm *= b[i];
    for(int i = 1; i <= k; i++) {
        ll tp = lcm / b[i];
        exgcd(tp, b[i], x, y);
        x = (x % b[i] + b[i]) % b[i];
        ans = (ans + tp * x * a[i]) % lcm;
    }
    return (ans + lcm) % lcm;
}

int main(int argc, const char * argv[]) {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> g;
    if (g % P == 0) {
        cout << "0\n";
        return 0;
    }
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            d.push_back(i);
            if (i * i != n) {
                d.push_back(n / i);
            }
        }
    }
    sort(d.begin(), d.end());

    for (int i = 1; i <= 4; i++) {
        for (int a : d) {
            (x[i] += Lucas(n, a, (int)Mo[i])) %= Mo[i];
        }
    }
    ll X = crt(x, Mo, 4);
    cout << ksm(g, X, P) << endl;

    return 0;
}