感觉自己的脑子要瓦特了…..

题目大意

对于所有的k($k | n$),求

$$
g^{\sum_{k|n} C_n^k}
$$

solution

我们首先根据欧拉定理的推论：
$$
a^p\equiv a^{p\ \bmod\ \varphi(n)}(\bmod n)
$$
即可确定$\sum_{k|n}C_n^k$的模数$\varphi(n)$，又因为n为一个极大的质数，所以$\varphi(n) = n -1$(我竟然兴奋的上了一个杜教筛，唉……)，但n过于庞大，达到了$1e9$的级别，所以我们还得运用卢卡斯定理：
$$
C_a^b = C_{a / p}^{b / p} * C_{a\ \bmod\ p} ^ {b\ \bmod\ p}, p\in{primes}
$$
这个时候，这个题的大体结构已经确定了，我们只需略略加一点小优化。不难发现p = 999911658时，我们无法使用卢卡斯（p不是质数），就算我们不顾一切使用了卢卡斯，它的效率也低的离谱（应该会溢出或者报错吧），我们接着考虑能否将p拆分成质数，再将各个因数所算出来的答案相加
运用暴力程序，我们成功的得到$999911658 = 2 * 3 * 4679 * 35617$,将其分别带入$Lucas$中求解答案，再利用中国剩余定理：
$$
\begin{cases}
&x\ \equiv &a_1(\bmod\ 2) \\
&x\ \equiv &a_2(\bmod\ 3) \\
&x\ \equiv &a_3(\bmod\ 4679)\\
&x\ \equiv &a_4(\bmod\ 45617)
\end{cases}
$$
然后我们就得到了最小的非负整数，直接快速幂计算答案即可。

代码

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int mod = 999911658, N = 1e6 + 5;
int n, g;
const int p[5] = {0, 2, 3, 4679, 35617};
template <class T>
inline void read(T& res)
{
	res = 0; bool flag = 0;
	char c = getchar();
	while(c < '0' || c > '9')
	{
		if(c == '-') flag = 1;
		c = getchar();
	}
	while('0' <= c && c <= '9')
		res = (res << 3) + (res << 1) + c - '0', c = getchar();
	if(flag) res = -res;
}
LL ans[N];
LL fac[N];
void init(int x)//对不同模数的乘积进行线性预处理
{
	fac[0] = 1;
	for(int i = 1;i <= x;i ++)
		fac[i] = fac[i - 1] * i % x;
}
LL qpow(LL x, LL b, LL k)
{
	LL res = 1;
	while(b)
	{
		if(b & 1) res = (res * x) % k;
		x = (x * x) % k;
		b >>= 1;
	}
	return res;
}
LL C(int a, int b, int k)
{
	if(a < b) return 0;
	return fac[a] * qpow(fac[b], k - 2, k) % k * qpow(fac[a - b], k - 2, k) % k;
}
LL lucas(int b, int a, int k)
{
	if(b < a) return 0;
	if(b <= 0) return 1;
	return lucas(b / k, a / k, k) * C(b % k, a % k, k) % k;
}
LL res = 0;
void CRT()//有些奇怪的中国剩余定理
{
	for(int i = 1;i <= 4;i ++)
	{
		res = (res + ans[i] * (mod / p[i]) % mod * qpow(mod / p[i], p[i] - 2, p[i])) % mod;
	}
}
int main()
{
	read(n), read(g);
	if(g % (mod + 1) == 0)
	{
		puts("0");
		return 0;
	}
	for(int k = 1;k <= 4;k ++)
	{
		init(p[k]);
		for(int i = 1;i <= sqrt(n);i ++)
		{
			if(n % i == 0)
			{
				ans[k] = (ans[k] + lucas(n, i, p[k]) % p[k]) % p[k]; 
				if(i * i != n)
					ans[k] = (ans[k] + lucas(n, n / i, p[k]) % p[k]) % p[k];
			}
		}
	}
	CRT();
	printf("%lld", qpow(g, res, mod + 1));
	return 0;
}

Luckyleaves's Blog

P2480 古代猪文

题目大意

solution

代码