题目链接

题意：

Sol：

首先当 q q q为 999911659 999911659 999911659时，答案为 0 0 0.
否则的话，因为 999911659 999911659 999911659是质数，根据欧拉定理的推论有：
q ∑ d ∣ n C n d ≡ q ∑ d ∣ n C n d   m o d   999911658 (   m o d     999911659 ) q^{\sum_{d|n} C_n^d} \equiv q^{\sum_{d|n} C_n^d \bmod 999911658} ( \bmod \ 999911659) q∑d∣n​Cnd​≡q∑d∣n​Cnd​mod999911658(mod 999911659)
因此我们主要计算：
∑ d ∣ n C n d   m o d   999911658 \sum_{d|n} C_n^d \bmod 999911658 d∣n∑​Cnd​mod999911658
尝试将新模数分解质因数可以发现：
999911658 = 2 × 3 × 4679 × 35617 999911658 = 2 × 3 × 4679 × 35617 999911658=2×3×4679×35617四个质数的指数都是 1 1 1.
那么我们枚举 n n n的约数 d d d，利用 l u c a s lucas lucas定理求组合数。
l u c a s lucas lucas定理：

如果p是质数，则对于任意整数 1 ≤ m ≤ n 1 \le m \le n 1≤m≤n，有：
C n m ≡ C n   m o d   p m   m o d   p ∗ C n / p m / p (   m o d     p ) C_n^m \equiv C_{n \bmod p}^{m\bmod p} * C_{n / p}^{m/p}(\bmod \ p) Cnm​≡Cnmodpmmodp​∗Cn/pm/p​(mod p)

分别求出 ∑ d ∣ n C n d \sum_{d|n} C_n^d ∑d∣n​Cnd​对 2 , 3 , 4679 , 35617 2, 3, 4679, 35617 2,3,4679,35617四个质数取模的结果，记作： a 1 , a 2 , a 3 , a 4 a_1, a_2, a_3, a_4 a1​,a2​,a3​,a4​。
计算过程中，可以先预处理 p p p以内的阶乘，然后利用 l u c a s lucas lucas快速求出组合数。
最后可以用中国剩余定理求解线性同余方程组：
{ x ≡ a 1 (   m o d   p 1 ) x ≡ a 2 (   m o d   p 2 ) x ≡ a 3 (   m o d   p 3 ) x ≡ a 4 (   m o d   p 4 ) \begin{cases} x \equiv a_1(\bmod p_1) \\ x \equiv a_2(\bmod p_2) \\ x \equiv a_3(\bmod p_3) \\ x \equiv a_4 (\bmod p_4) \end{cases} ⎩⎪⎪⎪⎨⎪⎪⎪⎧​x≡a1​(modp1​)x≡a2​(modp2​)x≡a3​(modp3​)x≡a4​(modp4​)​
就可以得到 ∑ d ∣ n C n d   m o d   999911658 \sum_{d|n} C_n^d \bmod 999911658 ∑d∣n​Cnd​mod999911658的最小非负正整数解 x x x，然后利用快速幂求解 q x   m o d   999911659 q^x \bmod 999911659 qxmod999911659就得到了问题的答案

Code:

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 999911658;

int qpow(int a ,int b, int p)
{
    int res = 1;
    while(b){
        if(b & 1) res = res * a % p;
        a = a % p * a % p;
        b >>= 1;
    }
    return res;
}

int inv(int x, int k){
    return qpow(x, k - 2, k);
}

int a[5], b[5] = {0, 2, 3, 4679, 35617};
const int N = 40010;
int jc[N];

void init(int k)
{
    jc[0] = 1;
    for(int i = 1; i <= k; ++i)
        jc[i] = (jc[i - 1] % k * i) % k;
}

int C(int n, int m, int p)
{
    if(n < m) return 0;
    return jc[n] % p * inv(jc[m], p) % p * inv(jc[n - m], p) % p;
}

int lucas(int n, int m, int p)
{
    if(n < p && m < p) return C(n, m, p);
    return C(n % p, m % p, p) * lucas(n / p, m / p, p) % p;
}

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

int CRT(int a[], int m[], int n)
{
    int ans = 0;
    int M = 1;
    for(int i = 1; i <= n; ++i) M *= m[i];
    for(int i = 1; i <= n; ++i)
    {
        int x, y;
        int MI = M / m[i];
        exgcd(MI,  m[i], x, y);
        x = ((x % m[i]) + m[i] ) % m[i];
        ans = (ans + a[i] % mod * MI % mod * x % mod) % mod;
    }
    return ans;
}

signed main()
{
    int n, q;
    cin >> n >> q;
    if(q % (mod + 1) == 0) {
        cout << 0 << endl;
        
    }
    else 
    {
        for(int k = 1; k <= 4; ++k)
        {
            init(b[k]);
            for(int i = 1; i <= n / i; ++i)
            {
                if(n % i == 0)
                {
                    a[k] = (a[k] + lucas(n, i, b[k])) % b[k];
                    if(i * i != n) a[k] = (a[k] + lucas(n ,n / i, b[k])) % b[k];
                }
            }
        }
        int x = CRT(a, b, 4);
        cout << qpow(q, x, mod + 1);
    }
}

最后：
我直呼好家伙，这几天少学一个（逆元，扩展欧几里得，欧拉定理，中国剩余定理，组合数，lucas ）就不会写这个了。我超 ！