HNU 13101 The Triangle Division of the Convex Polygon 组合数的因式分解求法

题意：

　　求第n-2个Catalan数模上 m。

思路：

　　Catalan数公式： Catalan[n] = C(n, 2n)/(n+1) = (2n)!/[(n+1)!n!]

　　因为m是在输入中给的，所以我们不能用求阶乘和其逆元的方法来求。因为当m不是素数的时候，可能不存在逆元。

　　这里，我们把阶乘做质因数分解，然后上下两边约分，即可求出解。

　　怎么来把这个n!因式分解呢？我们知道 n!中某个因子x的数量可以用log(n)的方法来求。

详见：这里

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <cmath>
 6 #include <algorithm>
 7 #include <string>
 8 #include <queue>
 9 #include <stack>
10 #include <vector>
11 #include <map>
12 #include <set>
13 #include <functional>
14 #include <cctype>
15 #include <time.h>
16 
17 using namespace std;
18 
19 typedef __int64 ll;
20 
21 const int INF = 1<<30;
22 const int MAXN = 1e6+5;
23 /*
24 Catalan Number : C(n, 2n)/(n+1) = (2n)!/[(n+1)!n!]
25 */
26 
27 bool isPrime[MAXN];
28 int Prime[MAXN], primeCnt;
29 
30 int cnt[MAXN];
31 
32 ll myPow(ll x, ll y, ll mod) {
33     ll ret = 1;
34     while (y>0) {
35         if (y&1) ret = (ret*x)%mod;
36         x = (x*x)%mod;
37         y >>= 1;
38     }
39     return ret;
40 }
41 
42 void getPrime() {
43     primeCnt = 0;
44     for (int i = 2; i < MAXN; i++) if (!isPrime[i]) {
45         Prime[primeCnt++] = i;
46         for (ll j = (ll)i*i; j < MAXN; j += i)
47             isPrime[j] = true;
48     }
49 }
50 
51 inline void initFactor(int x) {
52     for (int i = 0; Prime[i] <= x; i++)
53             cnt[i] = 0;
54 }
55 
56 void getFactor(int x, int v) {
57     for (int i = 0; Prime[i]<=x; i++) {
58         int t = x;
59         while (t>0) {
60             cnt[i] += (t/Prime[i])*v;
61             t /= Prime[i];
62         }
63     }
64 }
65 
66 ll getAns(int x, ll mod) {
67     ll ret = 1;
68     for (int i = 0; Prime[i] <= x; i++)
69         ret = (ret*myPow(Prime[i], cnt[i], mod))%mod;
70     return ret;
71 }
72 
73 int main() {
74     #ifdef Phantom01
75         freopen("HNU13101.txt", "r", stdin);
76     #endif //Phantom01
77 
78     getPrime();
79     int n, m;
80     ll ans;
81     while (scanf("%d%d", &n, &m)!=EOF) {
82         n -= 2;
83         initFactor(2*n);
84         getFactor(2*n, 1);
85         getFactor(n+1, -1);
86         getFactor(n, -1);
87         printf("%I64d
", getAns(2*n, m));
88     }
89 
90     return 0;
91 }

View Code