首页 > 代码库 > BZOJ 1485 卡特兰数 数学

BZOJ 1485 卡特兰数 数学

思路:

通过打表观察 这是个卡特兰数

但是它mod的数不是质数 怎么办呢

把所有数分解质因数好了

线性筛出mindiv  顺着mindiv分解质因数

复杂度$O(nlogn)$

//By SiriusRen#include <cstdio>using namespace std;const int N=2000005;int n,p,prime[N],top,mindiv[N],cnt[N];void get_prime(){    for(int i=2;i<=2000000;i++){        if(!mindiv[i])prime[++top]=i,mindiv[i]=i;        for(int j=1;j<=top&&i*prime[j]<=2000000;j++){            mindiv[i*prime[j]]=prime[j];            if(i%prime[j]==0)break;        }    }}int main(){    get_prime();    scanf("%d%d",&n,&p);    for(int i=1;i<=n;i++){        int temp=i;        while(temp!=1)cnt[mindiv[temp]]--,temp/=mindiv[temp];    }    for(int i=n+2;i<=2*n;i++){        int temp=i;        while(temp!=1)cnt[mindiv[temp]]++,temp/=mindiv[temp];    }    long long ans=1;    for(int i=1;i<=2*n;i++)        for(int j=1;j<=cnt[i];j++)            ans=ans*i%p;    printf("%lld\n",ans);}

 

BZOJ 1485 卡特兰数 数学