求解巨大卡特兰数 C++实现（高精度乘法，质因数）_卡特兰数c++实现

计算卡特兰数由于结果会非常大，所以采用vector来对数据进行存储，同时使用高精度乘法来对结果进行运算。

输入样例1：

3

输出样例1：

5

输入样例2：

60000

输出样例2：

15264047992826020890059564020503619491920807903813203631701630729178036601123431956081763172005086064437378171085856348270195047840322071315586249468037063288912924833521206447385223239815754849499430814317553488695989395939016034717754954930597629301403451877250855583453035658343037751056147516168262728613125621440457080187728699516015251580361480317234583552773304925662093710049500591880706526645287027843825853026838506326866069089340880675086110643078873199743607812046377269374830636931064022624158937842060715653756350289282105457900557447999019182958410846000075036048311439244390201017502561676011762161832610362081994413479473481747588631024228210022107194711586639020572840657026801356342349301970983845620590307890042640429652223447156259254085950978990838128967404108642194340566399015409237792443321836101739258225146297277707673259590481787041226512699580609879223048416896611198388926871118042237445798575218190889507697324073353469572153216379846717154657084359877443217220407891463237108631971711322423415737513715700712285185578723408056343704908012524522932357252401532294386838536606841885157332377650632598830806612356849675726861433471565810188421895161022690809142280631255727551567322355154316032031334682592881832711438914600881625986841786930606938465526747750162136733777615656940880630175322763063686713429600942869909882006324890992600757021249755170962532342659581409251101257611299380096201893747672619158693361173120345837335752172951108979801508486303760881776110521794874947049384526009316581930762889307835299763467364886716277043656364444946361836692808460373292943418902092350513972249633333526315775563488757450379964456736515808264879905004230534593781109574894456520360597033088396117407191537407960084755896129937422580364645350970923043175275608553863063034185304820099728882348076087091046847607369447602839182479597758200220394528783218627278505381295925388754693014512295336206969242636542407402296640430007153452676943101104162142084655623250701393…

#include<bits/stdc++.h>
using namespace std;

const int N = 6e5+10,mod = 1e8;   //采用long long int 进行压缩，加快运行速度
typedef long long LL;
int primes[N],co;
bool st[N];
void p(int n)
{
    co=0;   
    for(int i=2;i<=n;i++)
    {
        if(!st[i]) primes[co++]=i;
        for(int j=0;primes[j]<=n/i;j++)
        {
            st[primes[j]*i]=1;
            if(i % primes[j]==0) break;
        }
    }
}

int calc(int n,int pr)
{
    int s=0;
    while(n>0)
    {
        s+=n/pr;
        n/=pr;
    }
    return s;
}

vector<LL> mul(vector<LL> a,int b)   //高精度乘法计算结果
{
    vector<LL> c;
    LL t=0;
    for(int i=0;i<a.size();i++)
    {
        t+=a[i]*b;
        c.push_back(t%mod);
        t/=mod;
    }
    while(t)
    {
        c.push_back(t%mod);
        t/=mod;
    }
    return c;
}

int main()
{
        int a,b,n; 
        scanf("%d",&n);
        a = 2*n,b=n;
        p(a);
        int num[N];
        for(int i=0;i<co;i++)
        {
            int pr = primes[i];
            num[i] = calc(a,pr) - 2*calc(b,pr); 
        }
        int k=n+1;
        for(int i=0;i<co && primes[i]<=k;i++)
        {
        	int pr = primes[i],sum=0;
        	while(k%pr==0)
        	{
        		sum++;
        		k/=pr;
			}
			num[i]-=sum;
		}
		
        vector<LL> ans;
        ans.push_back(1);
        for(int i=0;i<co;i++)
        {
            while(num[i]--) ans = mul(ans,primes[i]);
        }
        printf("%lld",ans.back());
        for(int i=ans.size()-2;i>=0;i--) printf("%08lld",ans[i]);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84