题意

给定 $n,G$，求 $G^{\sum_{d|n} C_n^d} \bmod 999911659$ 的值。

$1 \le n,G \le 10^9$。

分析

设 $P = 999911659$，我们只要求 $\sum_{d|n} C_n^d \bmod P - 1$（费马小定理）。但是 $P - 1$ 不是质数，就算我们 $O(\sqrt{n})$ 枚举了 $d$，也不好在一个较优的时间复杂度内求出 $C_{n,d}$，因为预处理阶乘是 $O(n)$ 的。考虑 Lucas 定理。

因为这里 $P - 1$ 不是质数，所以要用到 exLucas 的思想，去对 $P - 1$ 质因数分解。比较好的是，分解出来得到 $P - 1 = 2 \times 3 \times 4679 \times 3617$，没有带指数，所以不用计算素数幂模数意义下的阶乘，直接暴力 $O(p_i)$ 即可，这里 $p_i$ 表示质因数分解后的第 $i$ 项。

求完之后直接套 Lucas 求，这一部分就可以 $O(\sqrt{n}\log p_i)$ 得到在 $p_i$ 模数意义下的解，记为 $x_i$。

我们就只要求一个 $X$，使得满足下面的式子。

$$\left\{\begin{matrix}X \equiv x_1 \pmod{2}\\X \equiv x_2 \pmod{3}\\X \equiv x_3 \pmod{4679}\\X \equiv x_4 \pmod{35617}\end{matrix}\right.$$

这个直接 CRT 求即可。

但是你会发现写完后交上去是 $95 \text{pts}$。因为当 $G \equiv 0 \pmod P$ 的时候，费马小定理不成立，要直接输出 $0$。

最终时间复杂度就是 $O(\sqrt{n}\log p_i)$，有一个 $4$ 的常数。

#include <bits/stdc++.h>
using namespace std;
#define il inline
#define N 100005
il int rd(){
    int s = 0, w = 1;
    char ch = getchar();
    for (;ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') w = -1;
    for (;ch >= '0' && ch <= '9'; ch = getchar()) s = ((s << 1) + (s << 3) + ch - '0');
    return s * w;
}
const int P = 999911658;
int n, G, p[5] = {0, 2, 3, 4679, 35617}, x[5], fact[N], inv_fact[N], ans;
il int ksm(int x, int r, int P){
    int ans = 1;
    for (; r; x = 1ll * x * x % P, r >>= 1) if (r & 1) ans = 1ll * ans * x % P;
    return ans;
}
int C(int n, int m, int P){return (n < m ? 0 : 1ll * fact[n] * inv_fact[m] % P * inv_fact[n - m] % P);}
int Lcs(int n, int m, int P){return (n < m ? 0 : !n ? 1 : 1ll * Lcs(n / P, m / P, P) * C(n % P, m % P, P) % P);}
int main(){
    n = rd(), G = rd();
    if (G % (P + 1) == 0) return 0 & puts("0");
    for (int k = 1; k <= 4; k++){
        fact[0] = 1;
        for (int i = 1; i < p[k]; i++) fact[i] = 1ll * fact[i - 1] * i % p[k];
        inv_fact[p[k] - 1] = ksm(fact[p[k] - 1], p[k] - 2, p[k]);
        for (int i = p[k] - 2; i >= 0; i--) inv_fact[i] = 1ll * inv_fact[i + 1] * (i + 1) % p[k];
        for (int i = 1; i * i <= n; i++) if (n % i == 0){
            x[k] = (x[k] + Lcs(n, i, p[k])) % p[k];
            if (i * i != n) x[k] = (x[k] + Lcs(n, n / i, p[k])) % p[k];
        }
    }
    for (int i = 1; i <= 4; i++) ans = (ans + 1ll * x[i] * (P / p[i]) % P * ksm(P / p[i], p[i] - 2, p[i]) % P) % P;
    printf ("%d\n", ksm(G, ans, P + 1));
    return 0;
}