poj3421 X-factor Chains——分解质因数

好久没有独立A题了...做点水题还是有助于提升自信心的；

这题就是把 x 质因数分解，质因数指数的和 sum 就是最长的长度，因为每次至少乘一个质因数；

排列方式就是从 sum 个位置里给第一种质因数选几个位置，再在剩下的里面给第二种质因数选几个位置...

也就是 ans = ∏(1<=i<=cnt) C(n,pc[i])，n -= pc[i]，其中 cnt 是质因数(种类)个数，pc 是每种质因数的指数，n 就是目前剩下几个位置。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

typedef long long ll;

int x,p[],pc[],cnt;

void divide(int n)

{

    cnt=;

    memset(pc,,sizeof pc);

    for(int i=;i*i<=n;i++)

        if(n%i==)

        {

            p[++cnt]=i;

            while(n%i==)pc[cnt]++,n/=i;

        }

    if(n>)p[++cnt]=n,pc[cnt]=;

}

ll C(int n,int m)

{

    if(n<m)return ;

    m=min(m,n-m);

    ll a=,b=;

    for(int i=n-m+;i<=n;i++)a*=i;

    for(int i=;i<=m;i++)b*=i;

    return a/b;

}

int main()

{

    while(~scanf("%d",&x))

    {

        divide(x);

        int sum=; ll ans=;

        for(int i=;i<=cnt;i++)sum+=pc[i];

        int n=sum;

        for(int i=;i<=cnt;i++)

        {

            ans*=C(n,pc[i]);

            n-=pc[i];

        }

        printf("%d %lld\n",sum,ans);

    }

    return ;

}

巴特西

poj3421 X-factor Chains——分解质因数

最新文章

热门文章