Luogu 2480 古代猪文

题解

---

question

求

$$G^{\sum_{d|N}C_{N}{d}} \bmod 999911658$$

---

解

由费马小定理

$$Answer = G^{\sum_{d|N}C_{N}^{d} \bmod 999911657} \bmod 999911658$$

$999911658 = 2 * 3 * 4679 * 35617$

先求质数部分, 记 $x = \sum_{d|N}C_{N}^{d}$
得同余方程组

$$\begin{equation} \left \{ \begin{aligned} & x \equiv m_1 (\bmod 2) \\ & x \equiv m_2 (\bmod 3) \\ & x \equiv m_3 (\bmod 4629) \\ & x \equiv m_4 (\bmod 35617) \\ \end{aligned} \right. \end{equation}$$

$Lucas$ 定理求 $m_i$
$CRT$ 合并
$ksm$ 求 $G^{x} \bmod 999911658$

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 999911659, MOD = 999911658;
int n, g, num[4], prime[4] = {2, 3, 4679, 35617}, fact[40000] = {1};
int qpow(ll a, int b, int p) {
    int ans = 1;
    for (; b; a = a * a % p, b >>= 1) {
        if (b & 1) {
            ans = ans * a % p;
        }
    }
    return ans;
}
int C(int n, int m, int p) {
    if (n < m) return 0;
    return fact[n] * qpow(fact[n - m] * fact[m], p - 2, p) % p;
}
int lucas(int n, int m, int p) {
    if (m == 0) return 1;
    return C(n % p, m % p, p) * lucas(n / p, m / p, p) % p;
}
int crt() {
    int ans = 0;
    for (int i = 0; i < 4; i++) {
        int tmp = MOD / prime[i];
        ans = (ans + 1LL * num[i] * tmp % MOD * qpow(tmp, prime[i] - 2, prime[i]) % MOD) % MOD;
    }
    return ans;
}
int main() {
    scanf("%d %d", &n, &g);
    if (g == mod) {
        printf("0\n");
        return 0;
    }
    for (int i = 0; i < 4; i++) {
        fact[0] = 1;
        for (int j = 1; j <= prime[i]; j++) {
            fact[j] = fact[j - 1] * j % prime[i];
        }
        for (int d = 1; d * d <= n; d++) {
            if (n % d != 0) continue;
            num[i] = (num[i] + lucas(n, d, prime[i])) % prime[i];
            if (n / d == d) continue;
            num[i] = (num[i] + lucas(n, n / d, prime[i])) % prime[i];
        }
    }
    printf("%d\n", qpow(g, crt(), mod));
    return 0;
}