2010-1166

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

这道题目，首先对于输入n 进行素因数分解，假设有m个素因数（相同的素因数重复计算，比如4的素因数有2个），对于这个m个数的每一种不同的排列，其中不同的Factor Tree的个数就是有m个叶子节点的二叉树个数，也就是m的卡特朗数.

所以这题的答案就是m个有重复数的排列乘上m的卡特朗数。


{{{
#!cpp
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;


typedef unsigned  long long ll;

typedef vector<int> vi;
vi prime;

ll gao( const vi &a ) {
    ll res=1;
    int m =0;
    for(int i=0;i<a.size();++i){
        m+= a[i];
    }

    for(int i=0;i<a.size();++i){
        for(int j=1;j<=a[i];++j){
            res = res * m / j ;
            --m;
        }
    }
    return res;
}


ll gao( int n , int m ) {

    ll res = 1; 
    for(int i=0;i<m;++i){
        res = res * ( n-i ) / (i+1);
    }
    return res;

}

ll gao( int n) {

    vi p ;
    int t=n;
    int cnt=0;
    int size = prime.size();
    for(int i=0;i<size&&prime[i]*prime[i]<=n;++i){

        int tmp =0;
        while ( t % prime[i] == 0 ) {
            ++tmp;
            t/=prime[i];
        }
        if ( tmp >0 ) p.push_back(tmp);
        cnt+=tmp;
    }

    if (t > 1 ) ++cnt,p.push_back(1);

    ll res = gao(2*cnt-2,cnt-1);
    res/=cnt;

    res *= gao(p);


    return res;

}


void gao(){
    bool  g[31622+1];
    memset(g,true,sizeof(g));

    for(int i = 2; i*i <= 31622; ++i ) if(g[i]){
        for(int j=i*i;j<=31622;j+=i)g[j]=false;
    }

    for(int i=2;i<=31622;++i){
        if ( g[i] ) prime.push_back(i);
    }
}

int main(){

    int n;
    gao();
    while ( scanf("%d",&n)!=EOF ) {
        printf("%llu\n",gao(n));
    }

    return 0;

}


}}}

这道题目，首先对于输入n 进行素因数分解，假设有m个素因数（相同的素因数重复计算，比如4的素因数有2个），对于这个m个数的每一种不同的排列，其中不同的Factor Tree的个数就是有m个叶子节点的二叉树个数，也就是m的卡特朗数.

所以这题的答案就是m个有重复数的排列乘上m的卡特朗数。

#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;
typedef unsigned  long long ll;
typedef vector<int> vi;
vi prime;
ll gao( const vi &a ) {
    ll res=1;
    int m =0;
    for(int i=0;i<a.size();++i){
        m+= a[i];
    }
    for(int i=0;i<a.size();++i){
        for(int j=1;j<=a[i];++j){
            res = res * m / j ;
            --m;
        }
    }
    return res;
}
ll gao( int n , int m ) {
    ll res = 1; 
    for(int i=0;i<m;++i){
        res = res * ( n-i ) / (i+1);
    }
    return res;
}
ll gao( int n) {
    vi p ;
    int t=n;
    int cnt=0;
    int size = prime.size();
    for(int i=0;i<size&&prime[i]*prime[i]<=n;++i){
        int tmp =0;
        while ( t % prime[i] == 0 ) {
            ++tmp;
            t/=prime[i];
        }
        if ( tmp >0 ) p.push_back(tmp);
        cnt+=tmp;
    }
    if (t > 1 ) ++cnt,p.push_back(1);
    ll res = gao(2*cnt-2,cnt-1);
    res/=cnt;
    res *= gao(p);
    return res;
}
void gao(){
    bool  g[31622+1];
    memset(g,true,sizeof(g));
    for(int i = 2; i*i <= 31622; ++i ) if(g[i]){
        for(int j=i*i;j<=31622;j+=i)g[j]=false;
    }
    for(int i=2;i<=31622;++i){
        if ( g[i] ) prime.push_back(i);
    }
}
int main(){
    int n;
    gao();
    while ( scanf("%d",&n)!=EOF ) {
        printf("%llu\n",gao(n));
    }
    return 0;
}