古代猪文

数学真的好ex

题面

(1 leqslant q, n leqslant 10^9), 计算 (q^{sum_{d|n}C_n^d mod 999911658}(mod 999911659))

题解

注意到指数取模的非质数, 所以我们可以分别取模, 最后用中国剩余定理合并

求(C_n^m)时, 使用Lucas定理

ps:如果想要化简, 根据欧拉定理去化简

const int mod[] = {2, 3, 4679, 35617, 999911659, 999911658};

int n, m, _, k;
int inv[N] = {0, 1}, a[N] = {1, 1}, b[N] = {1, 1};
VI fa;

int power(int a, int b, int mod) {
    int ans = 1;
    for (; b; b >>= 1, a = (ll)a * a % mod)
        if (b & 1) ans = (ll)ans * a % mod;
    return ans;
}

int exgcd(int a, int b, int& x, int& y) {
    if (b == 0) { x = 1, y = 0; return a; }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int C(int x, int y, int p) {
    if (y > x) return 0;
    return (ll)a[x] * b[y] % p * b[x - y] % p;
}

int lucas(int x, int y, int p) {
    if (y == 0) return 1;
    return (ll)C(x % p, y % p, p) * lucas(x / p, y / p, p) % p;
}

void work(int p) {
    rep (i, 2, p) {
        inv[i] = (ll)(p - p / i) * inv[p % i] % p;
        a[i] = (ll)a[i - 1] * i % p;
        b[i] = (ll)b[i - 1] * inv[i] % p;
    }
}

int cal(int p) {
    work(p);
    int res = 0;
    for (int i : fa) res = (res + (ll)lucas(n, i, p)) % p;
    return res;
}

void init() {
    for (int i = 1; i * i <= n; ++i)
        if (n % i == 0) {
            fa.pb(i);
            if (i * i == n) break;
            fa.pb(n / i);
        }
}

int main() {
    IO;
    cin >> n >> m;
    if (m == mod[4]) { cout << 0; return 0; }
    init();

    rep (i, 0, 3) {
        int x, y, m = mod[4] / mod[i], a = cal(mod[i]);
        exgcd(m, mod[i], x, y);
        k = (k + ((ll)a * m % mod[5] * x % mod[5] + mod[5]) % mod[5]) % mod[5];
    }

    cout << power(m, k, mod[4]);
    return 0;
}