题意
求
\[g^{\sum\limits_{d | n} C_n^d} \bmod 999911659 \]\(n, g \le 10^9\)
一道非常好的数论题，用到了基本所有的基础数论知识。
需要使用到的数论知识
- 欧拉定理
- 逆元
- lucas 定理
- 中国剩余定理
对式子变形
先令 \(\sum\limits_{d | n} C_n^d = x\)。
首先整个式子是可以用快速幂搞出来的，所以我们考虑怎么求出那个巨大的系数。
由于 \(999911659\) 是质数，那么考虑使用欧拉定理和它的推论来化简。
欧拉定理：若 \(\gcd(a, m) = 1\)，则 \(a^\varphi(m) \equiv 1 \pmod m\)。
推论：
\[a^b \equiv \begin{cases} a^{b \bmod \varphi(m)} & , \gcd(a, m) = 1 \\ a^b &, b < \varphi(m) \\ a^{b \bmod \varphi(m) + arphi(m)} &, b \ge \varphi(m) \end{cases} \]那么原式就变成了
\[g^{x \bmod 999911658} \bmod 999911659 \]分解模数
求组合数取模考虑使用 lucas 定理，但这个模数太大了，lucas 定理的时间复杂度是 \(\mathcal{O}(p \log_np)\) 的，会爆掉。
考虑对其分解质因数。
\[999911658 = 2 \times 3 \times 4679 \times 35617 \]这个数非常非常的好，因为每个质因数（也就是后面的模数）的指数都是 \(1\)，可以直接上中国剩余定理。
如果不是上面这样，还得用扩展中国剩余定理。
我们能用 lucas 分别求出那个系数模上面四个质数的余数 \(a_1 \sim a_4\)
\[\begin{cases} x \equiv a_1 \pmod 2 \\ x \equiv a_2 \pmod 3 \\ x \equiv a_3 \pmod {4679} \\ x \equiv a_4 \pmod {35617} \end{cases} \]用 CRT 求出结果
套模板即可。
一个细节
上述算法最开始的化简的要求是 \(\gcd(a, m) = 1\)。
数据范围内有可能出现 \(g = 999911659\) 的情况，需要特判。
代码实现
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int inf = 0x3f3f3f3f;
const LL infLL = 0x3f3f3f3f3f3f3f3fLL;
const int P = 999911658;
int mi[] = {2, 3, 4679, 35617};
int a[4];
int n, g;
int qpow(int a, int b, int P)
{
int res = 1;
while (b)
{
if (b & 1) res = (LL)res * a % P;
a = (LL)a * a % P;
b >>= 1;
}
return res;
}
int C(int n, int m, int P)
{
if (n < m) return 0;
if (m > n - m) m = n - m;
int c1 = 1, c2 = 1;
for (int i = 1; i <= m; i ++ )
{
c1 = (LL)c1 * (n - i + 1) % P;
c2 = c2 * i % P;
}
return (LL)c1 * qpow(c2, P - 2, P) % P;
}
int lucas(int n, int m, int P)
{
return !m ? 1 : (LL)C(n % P, m % P, P) * lucas(n / P, m / P, P) % P;
}
int crt()
{
int m = P;
int res = 0;
for (int i = 0; i < 4; i ++ )
{
int M = m / mi[i];
res = (res + (LL)M * qpow(M, mi[i] - 2, mi[i]) * a[i]) % P;
}
return res;
}
int main()
{
cin >> n >> g;
if (g % (P + 1) == 0) return puts("0") & 1;
for (int i = 0; i < 4; i ++ )
{
for (int j = 1; j * j <= n; j ++ )
{
if (n % j) continue;
a[i] = ((LL)a[i] + lucas(n, j, mi[i]));
if (j == n / j) continue;
a[i] = ((LL)a[i] + lucas(n, n / j, mi[i]));
}
}
cout << qpow(g, crt(), P + 1) << endl;
return 0;
}