Description

[SDOI2010]古代猪文

Solution

给\(n\)，\(G\)，求\(G^{\sum_{d|n}C^{d}_{n}}\:mod\:999911659\)
先套一下欧拉定理，因为\(999911659\)是质数，所以，
\(G^{\sum_{d|n}C^{d}_{n}}\:mod\:999911659\)=\(G^{\sum_{d|n}C^{d}_{n}\:mod\:999911658}\:mod\:999911659\)
我们先求\(\sum_{d|n}C^{d}_{n}\:mod\:999911658\)
我们发现，\(999911658=2*3*4679*35617\)，四个质数相乘，而且质数的次数都为\(1\)
用\(Lucas\)定理求出\(\sum_{d|n}C^{d}_{n}\)分别在\(2\)，\(3\)，\(4679\)，\(35617\)下的余数\(a1\)，\(a2\)，\(a3\)，\(a4\)
设答案为\(x\)，得到方程
\(\left\{ \begin{aligned} x&\equiv a1&(mod&\:2)\\ x&\equiv a2&(mod&\:3)\\ x&\equiv a3&(mod&\:4679)\\ x&\equiv a4&(mod&\:35617)\\ \end{aligned} \right.\)
再套一下中国剩余定理的板子，求出\(x\)，再用一个快速幂，就可以求出答案了

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 999911659
#define MoD 999911658
#define MOD1 2
#define MOD2 3
#define MOD3 4679
#define MOD4 35617
ll M1, M2, M3, M4, n, G, a1, a2, a3, a4, x, sum;
ll h1[MOD1 + 10], h2[MOD2 + 10], h3[MOD3 + 10], h4[MOD4 + 10];
inline ll read() {
    ll s = 0, w = 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
    for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
    return s * w;
}
inline ll Pow(ll a, ll b, ll p) {
    ll ans = 1;
    while (b) {
        if (b % 2) (ans *= a) %= p;
        (a *= a) %= p;
        b /= 2;
    }
    return ans;
}
inline ll Inv(ll a, ll p) {
    return Pow(a, p - 2, p);
}
inline ll C(ll n, ll m, ll p) {
    if (m > n) return 0;
    if (p == MOD1) return h1[n] * Inv(h1[m], p) % p * Inv(h1[n - m], p) % p;
    if (p == MOD2) return h2[n] * Inv(h2[m], p) % p * Inv(h2[n - m], p) % p;
    if (p == MOD3) return h3[n] * Inv(h3[m], p) % p * Inv(h3[n - m], p) % p;
    if (p == MOD4) return h4[n] * Inv(h4[m], p) % p * Inv(h4[n - m], p) % p;
}

ll Lucas(ll n, ll m, ll p) {
    if (!m) return 1;
    return Lucas(n / p, m / p, p) * C(n % p, m % p, p) % p;
}
inline void Init() {
    h1[0] = 1; for (register ll i = 1; i <= MOD1; i++) h1[i] = (h1[i - 1] * i) % MOD1;
    h2[0] = 1; for (register ll i = 1; i <= MOD2; i++) h2[i] = (h2[i - 1] * i) % MOD2;
    h3[0] = 1; for (register ll i = 1; i <= MOD3; i++) h3[i] = (h3[i - 1] * i) % MOD3;
    h4[0] = 1; for (register ll i = 1; i <= MOD4; i++) h4[i] = (h4[i - 1] * i) % MOD4;  
}
int main() {
    //freopen("pa.in", "r", stdin);
    //freopen("2.out", "w", stdout);
    M1 = MoD / MOD1;
    M2 = MoD / MOD2;
    M3 = MoD / MOD3;
    M4 = MoD / MOD4;
    Init();
    n = read(), G = read();
    for (register ll i = 1; i <= sqrt(n); i++)
        if (n % i == 0) {
            a1 = Lucas(n, i, MOD1), a2 = Lucas(n, i, MOD2), a3 = Lucas(n, i, MOD3), a4 = Lucas(n, i, MOD4);
            x = ((a1 % MoD * M1 % MoD * Inv(M1, MOD1) % MoD) +
                 (a2 % MoD * M2 % MoD * Inv(M2, MOD2) % MoD) +
                 (a3 % MoD * M3 % MoD * Inv(M3, MOD3) % MoD) +
                 (a4 % MoD * M4 % MoD * Inv(M4, MOD4) % MoD)) % MoD;
            (sum += x) %= MoD;
            if (i * i == n) continue;
            a1 = Lucas(n, n / i, MOD1), a2 = Lucas(n, n / i, MOD2), a3 = Lucas(n, n / i, MOD3), a4 = Lucas(n, n / i, MOD4);
            x = ((a1 % MoD * M1 % MoD * Inv(M1, MOD1) % MoD) +
                 (a2 % MoD * M2 % MoD * Inv(M2, MOD2) % MoD) +
                 (a3 % MoD * M3 % MoD * Inv(M3, MOD3) % MoD) +
                 (a4 % MoD * M4 % MoD * Inv(M4, MOD4) % MoD)) % MoD;
            (sum += x) %= MoD;
        }
    printf("%lld", Pow(G, sum, MOD));
    return 0;
}