洛谷 P2480 【[SDOI2010]古代猪文】 题解

$\texttt{Description}$

给定 $n,g$，求 $g^{\sum_{k\mid n}\tbinom{n}{k}}\texttt{ mod } 999911659$ 。

$\texttt{Data Range:}1\le n,g\le 10^9$

$\texttt{Solution}$

CRT板题（

这飞上天的指数显然考虑降冥。根据欧拉定理，$g^{\sum_{k\mid n}\tbinom{n}{k}}\texttt{ mod } 999911659=g^{\sum_{k\mid n}\tbinom{n}{k}\texttt{ mod }999911658}\texttt{ mod } 999911659$。

现在计算出指数后套上快速冥即可。因此考虑计算 $\sum_{k\mid n}\tbinom{n}{k}\texttt{ mod }999911658$。

啥啥啥 $\texttt{99911658}$ 是合数？我不会扩卢别吓我。

然而你分解了质因数发现 $99911658=2\times 3\times 4679\times 35617$。好像所有质因数的指数都是1欸？

那么就好做起来了。令 $S=\sum_{k\mid n}\tbinom{n}{k}$，则分别算出 $S\texttt{ mod } 2,S\texttt{ mod } 3,S\texttt{ mod } 4679,S\texttt{ mod } 35617$ ，用CRT合并解即可。

组合数对指数取模求和用 Lucas 应该都会吧（大雾

注意 Lucas 计算 $\tbinom{n}{m}$ 时特判 $n<m$ 的情况。

我怎么会轻易告诉你我交了十几发呢。

$\texttt{Code}$

#include <iostream>
#define int long long

const int MOD = 999911659LL;
const int f[] = {2, 3, 4679, 35617};
int fact[360000], a[4];
int qpow(int a, int b, int mod) {
	int ret(1LL);
	while (b) {
		if (b & 1) ret = ret * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ret;
}
int inv(const int a, const int mod) {
	return qpow(a, mod - 2, mod);
}
inline int C(const int n, const int m, const int p) {
	if (n < m) return 0LL;
	return fact[n] * inv(fact[m], p) % p * inv(fact[n - m], p);
}
inline int Lucas(const int n, const int m, const int p) {
	if (n < m) return 0LL;
	return m == 0 ? 1 : C(n % p, m % p, p) * Lucas(n / p, m / p, p) % p;
}
inline int CRT() {
	int sum(MOD - 1), ans(0LL);
	for (int i(0); i <= 3; ++ i) {
		int t(sum / f[i]);
		ans = (ans + a[i] * t % sum * inv(t, f[i]) % sum) % sum;
	}
	return ans;
}

signed main() {
	fact[0] = 1LL;
	int n, g;
	scanf("%lld%lld", &n, &g);
	if (g == MOD) return putchar('0'), 0;
	for (int i(1); i <= 35617; ++ i) fact[i] = fact[i - 1] * i % MOD;
	for (int j(0); j <= 3; ++ j) {
		for (int i(1); i <= f[j]; ++ i) fact[i] = fact[i - 1] * i % f[j];
		for (int i(1); i * i <= n; ++ i) if (n % i == 0) {
			a[j] = (a[j] + Lucas(n, i, f[j])) % f[j];
			if (i * i != n) a[j] = (a[j] + Lucas(n, n / i, f[j])) % f[j];
		}
	}
	printf("%lld", qpow(g, CRT(), MOD));
	return 0;
}