bjfu1238 卡特兰数取余

题目就是指定n，求卡特兰数Ca(n)%m。求卡特兰数有递推公式、通项公式和近似公式三种，因为要取余，所以近似公式直接无法使用，递推公式我简单试了一下，TLE。所以只能从通项公式入手。

Ca(n) = (2*n)! / n! / (n+1)!

思想就是把Ca(n)质因数分解，然后用快速幂取余算最后的答案。不过，算n!时如果从1到n依次质因数分解，肯定是要超时的，好在阶乘取余有规律，不断除素因子即可。

最后还是擦边过，可能筛法写得一般吧，也算是题目要求太柯刻。

/*

 * Author    : ben

 */

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <queue>

#include <set>

#include <map>

#include <stack>

#include <string>

#include <vector>

#include <deque>

#include <list>

#include <functional>

#include <numeric>

#include <cctype>

using namespace std;

#ifdef ON_LOCAL_DEBUG

#else

#endif

typedef long long LL;

const int MAXN = ;

const int N = ;

bool isPrime[N + ];//多用两个元素以免判断边界

int pn, pt[MAXN], num[MAXN];

void init_prime_table() {

    memset(isPrime, true, sizeof(isPrime));

    int p = , q, del;

    double temp;

    while (p <= N) {

        while (!isPrime[p]) {        p++;        }

        if (p > N) {//已经结束

            break;        }

        temp = (double) p;

        temp *= p;

        if (temp > N)

            break;

        while (temp <= N) {

            del = (int) temp;            isPrime[del] = false;

            temp *= p;        }

        q = p + ;

        while (q < N) {

            while (!isPrime[q]) {    q++;    }

            if (q >= N) { break;}

            temp = (double) p;

            temp *= q;

            if (temp > N)    break;

            while (temp <= N) {

                del = (int) temp;

                isPrime[del] = false;

                temp *= p;

            }

            q++;

        }

        p++;

    }

    pn = ;

    for (int i = ; i <= N; i++) {

        if (isPrime[i]) {

            pt[pn++] = i;

        }

    }

}

int modular_exp(int a, int b, int c) {

    LL res, temp;

    res =  % c, temp = a % c;

    while (b) {

        if (b & ) {

            res = res * temp % c;

        }

        temp = temp * temp % c;

        b >>= ;

    }

    return (int) res;

}

void getNums(int n) {

    int x =  * n;

    int len = pn;

    for (int i = ; i < len && pt[i] <= x; i++) {

        int r = , a = x;

        while (a) {

            r += a / pt[i];

            a /= pt[i];

        }

        num[i] = r;

    }

    x = n;

    for (int i = ; i < len && pt[i] <= x; i++) {

        int r = , a = x;

        while (a) {

            r += a / pt[i];

            a /= pt[i];

        }

        num[i] -= r;

    }

    x = n + ;

    for (int i = ; i < len && pt[i] <= x; i++) {

        int r = , a = x;

        while (a) {

            r += a / pt[i];

            a /= pt[i];

        }

        num[i] -= r;

    }

}

int main() {

#ifdef ON_LOCAL_DEBUG

    freopen("data.in", "r", stdin);

//    freopen("test.in", "r", stdin);

//    freopen("data.out", "w", stdout);

#endif

    int n, m;

    init_prime_table();

    while (scanf("%d%d", &n, &m) == ) {

        getNums(n);

        LL ans = ;

        int n2 =  * n;

        for (int i = ; ans && (i < pn) && pt[i] <= n2; i++) {

            if (num[i] > ) {

                ans = ans * (LL) modular_exp(pt[i], num[i], m);

                ans %= m;

            }

        }

        printf("%d\n", (int)ans);

    }

    return ;

}