洛谷P2480题解

题目链接

信息提取：

根据 “只要符合文献，每一种 都是有可能的” 和 “如果所有可能的 的所有情况数加起来为 的话” 可以推出 等于一个组合数数列的和，即

再根据 “那么他研究古代文字的代价将会是 ” 和 “只需要告诉他答案除以 的余数就可以了” 两句话即可得出最后的答案为：

解法阐述：

1. 欧拉定理的推论：

因为 是一个质数，所以欧拉定理的推论 () 成立，所以有：

而 的值是确定的，所以只要求出 即可

2. 处理组合数数列求和：

由于 和 的值都很大，应用卢卡斯定理 ( )求解，但是卢卡斯定理只适用于模数为质数且较小的时候，虽然可以用普适的扩展卢卡斯定理求解，但是 是一个非常特殊的数字

对 分解质因数：

注意到其中的所有质因子的次数均为 ，对于这样的模数进行的取模运算，我们可以列出如下的同余方程组进行等价的运算：

如果要求 ，其中

那么等价于求出同余方程组

在 范围内的解

所以可以用卢卡斯定理和中国剩余定理 () 求解

证明：

1> 模运算到同余方程组

由

可得 ，其中

即

所以 ，其中

因为 且

所以

2> 同余方程组到模运算

由 其中

可得 ，其中

当 ，其中 时，即 满足其他所有的同余方程时

有

所以

当且仅当 在 范围内是， 的值与 相等

3. 总结：

我们只需分别求出 模 个数的值，再用 合并，最后快速幂求答案即可

4. 注意：

时答案为

code:

// Problem: P2480 [SDOI2010] 古代猪文
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2480
// Memory Limit: 125 MB
// Time Limit: 1000 ms

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int mod = 999911659, N = 40000;
typedef long long ll;

int prime[4] = {2, 3, 4679, 35617};
int fact[N], infact[N];
int ans[4];

int qmi(int a, int k, int p)
{
	int res = 1;
	while(k)
	{
		if(k & 1) res = (ll) res * a % p;
		a = (ll) a * a % p;
		k >>= 1;
	}
	
	return res;
}

void init(int p, int n)
{
    fact[0] = 1, infact[0] = 1;
    for(int i = 1; i <= n; i ++ )
    {
        fact[i] = (ll)i * fact[i - 1] % p;
        infact[i] = (ll)infact[i - 1] * qmi(i, p - 2, p) % p;
    }
}

int C(int a, int b, int p)
{
	if(a > b) return 0;
	int res = (ll) fact[b] * infact[a] % p * infact[b - a] % p;
	return res;
}

int Lucas(int a, int b, int p)
{
	if(a < p && b < p) return C(a, b, p);
	return (ll) C(a % p, b % p, p) * Lucas(a / p, b / p, p) % p;
}

void CRT(int &res)
{
	int p = mod - 1;
	for(int i = 0; i < 4; i ++ )
	{
		int x = p / prime[i];
		res = (ll) (res + (ll) ans[i] * x % p * qmi(x, prime[i] - 2, prime[i]) % p) % p;
	}
}

int main()
{
	int n, g;
	cin >> n >> g;
	// 欧拉定理：a^(p - 1) 在mod n意义下与 a^p 同余
	
	int res = 0;
	for(int j = 0; j < 4; j ++ )
	{
		init(prime[j], prime[j]);
		int k = 0;
		for(int i = 1; i <= n / i; i ++ )
		{
			if(n % i == 0) 
			{
				k = (ll) (k + Lucas(i, n, prime[j])) % prime[j];
				if(i * i != n) k = (ll) (k + Lucas(n / i, n, prime[j])) % prime[j];
			}
		}
		ans[j] = k;
	}
	
	CRT(res);
	
	if(g % mod != 0) cout << qmi(g, res, mod) << endl;
	else cout << 0 << endl;
	
	return 0;
}