卡特兰数，扩欧求逆元
题目意思：
n个节点的二叉树，可以构成有 catalan[n] 种不同的二叉树。 sum[n] 是卡特兰数前 n项的总和。
每次给出两个数 n, m， 求 sum[n] % m 是多少。
本题要点：
1、n很大，如果用大数来存第 100000 个卡特兰数，肯定超时。
2、卡特兰数的 递推公式
h[i] = h[i - 1] * (4 * i - 2) / (i + 1)
要求每一个卡特兰数 对m的模， 这里有除法，需要 求 (i + 1) 在模 m的情况下的逆元。
3、扩展欧几里得算法，求逆元
同余式 ax = 1(mod m), 如果 a, m 互质， 那么必然存在x, 使得 ax = 1(mod m)成立。
x 就是 a 在模 m下的逆元。 式子 ax = 1(mod m)， 变形 ax - m*y = 1, 右扩展欧几里得算法，
直接求出x。
4、 本题中， (4 * i - 2) 与 m 不一定互质， (i + 1) 与 m 不一定互质，通过 m 进行因数分解来解决:
m 进行因数分解：
vector vc; // 存放 m 的各个素因子
5、 观察 式子 h[i] = h[i - 1] * (4 * i - 2) / (i + 1)， 第一个卡特兰数 h[1] = 1
然后全部展开的话， h[i] = 1 * (6 / 3) * (10 / 4) * (14 / 5) * … * ( (4 * i - 2) / (i + 1) )
分子部分 (4 * i - 2) 所有的乘积，必然能够整除 所有 分母部分 (i + 1) 的所有乘积。
然后对于分子 temp = (4 * i - 2) ，如果能整除m的某个素因子 vc[j], temp /= vc[j], 同时 cnt[j]++;
假设除剩下来的 是 fz , 那么 fz 与 m 互质。
然后对于分母 temp = (i + 1) ，如果能整除m的某个素因子 vc[j], temp /= vc[j], 同时 cnt[j]–;
假设除剩下来的 是 fm , 那么 fm 与 m 互质。 可以用扩展欧几里得算法， 求 fm 在模m下的逆元了。
对于每一个 cnt[j], 不会有负数的。具体实现看代码，比较明了。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int MaxN = 100010;
typedef long long LL;
LL n, m;
int cnt[MaxN]; //存放相应的次数
vector<LL> vc; // 存放 m 的各个素因子LL exgcd(LL a, LL b, LL&x, LL& y)
{
if(!b){
x = 1, y = 0;return a;}LL d = exgcd(b, a % b, x, y);LL z = x; x = y; y = z - y * (a / b);return d;
}LL inv(LL a, LL mod) // 求a在模 mod 的情况下的逆元
{
//逆元不存在的话，返回 -1 LL d, x, y;d = exgcd(a, mod, x, y);return d == 1? (x + mod) % mod : -1;
}void getPrime(int x)
{
for(int i = 2; i * i <= x; ++i){
if(x % i) continue;while(x % i == 0)x /= i;vc.push_back(i);}if(x > 1)vc.push_back(x);
}int main()
{
while(scanf("%lld%lld", &n, &m) != EOF){
if(n == 0 && m == 0)break;vc.clear();memset(cnt, 0, sizeof cnt);LL res = 1 % m, pre = 1;getPrime(m);for(int i = 2; i <= n; ++i){
LL fz = 4 * i - 2, fm = i + 1;int len = vc.size(); //处理 fzfor(int j = 0; j < len; ++j){
if(fz % vc[j] == 0){
while(fz % vc[j] == 0){
fz /= vc[j];cnt[j]++;}}}pre = pre * fz % m;for(int j = 0; j < len; ++j){
if(fm % vc[j] == 0){
while(fm % vc[j] == 0){
fm /= vc[j];cnt[j]--;}}}if(fm > 1)pre = pre * inv(fm, m) % m;LL tmp = pre;for(int j = 0; j < len; ++j){
for(int k = 1; k <= cnt[j]; ++k){
tmp = (tmp * vc[j]) % m;}}res = (res + tmp) % m;}printf("%lld\n", res);}return 0;
}/* 3 100 4 10 0 0 *//* 8 2 */