思路与算法

所需指数P=Σd|N C(N,d)，只需P模q−1，q=999911659为素数。q−1=2·3·4679·35617，先枚举N约数，对这四个素数分别用Lucas计算各组合数之和，再CRT合成P模q−1，最后模快速幂。若G被q整除，由P≥1直接输出0。

正确性说明

每种保留文字数d对应C(N,d)种选择，约数取遍全部可能，故指数公式正确。Lucas把每个组合数对素数的余数拆为数位组合数积；四个素因子互质，CRT唯一恢复指数模q−1。G不被素数q整除时费马小定理允许指数按q−1约简；整除时正指数必为0。两种情形覆盖全部输入。

复杂度

约数枚举O(sqrt N)，四个素数阶乘及逆阶乘初始化O(Σp)，每个约数组合数O(Σlog_p N)，模幂O(log q)。总O(sqrt N+Σp+τ(N)Σlog_p N)，空间O(max p+τ(N))。

易错点

模数统一为999911659，描述中尾随4是已公开纠正的笔误。指数取模q−1而非q；大组合数不能用普通阶乘除法。G%q0必须先处理，不能把正指数约为0后错误算成1。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 999911659, PHI = MOD - 1;
ll power(ll a, ll n, ll p) {
    ll r = 1;
    for (a %= p; n; n >>= 1, a = a * a % p)
        if (n & 1)
            r = r * a % p;
    return r;
}
int main() {
    ll n, g;
    cin >> n >> g;
    if (g % MOD == 0) {
        cout << 0 << '\n';
        return 0;
    }
    vector<ll> div;
    for (ll d = 1; d * d <= n; d++)
        if (n % d == 0) {
            div.push_back(d);
            if (d * d != n)
                div.push_back(n / d);
        }
    ll exponent = 0;
    for (int p : {2, 3, 4679, 35617}) {
        vector<ll> f(p, 1), iv(p, 1);
        for (int i = 1; i < p; i++)
            f[i] = f[i - 1] * i % p;
        iv[p - 1] = power(f[p - 1], p - 2, p);
        for (int i = p - 1; i; i--)
            iv[i - 1] = iv[i] * i % p;
        auto C = [&](ll x, ll y) {
            ll z = 1;
            while (x || y) {
                int a = x % p, b = y % p;
                if (b > a)
                    return 0LL;
                z = z * f[a] % p * iv[b] % p * iv[a - b] % p;
                x /= p;
                y /= p;
            }
            return z;
        };
        ll rem = 0;
        for (ll d : div)
            rem = (rem + C(n, d)) % p;
        ll part = PHI / p;
        exponent = (exponent + rem * part % PHI * power(part, p - 2, p)) % PHI;
    }
    cout << power(g, exponent, MOD) << '\n';
}