1628：X-factor Chain

时间限制: 1000 ms 内存限制: 524288 KB
提交数: 122 通过数: 68

【题目描述】

原题来自 POJ 3421

输入正整数 x

，求 x 的大于 1

的因子组成的满足任意前一项都能整除后一项的序列的最大长度，以及满足最大长度的序列的个数。

【输入】

多组数据，每组数据一行，包含一个正整数 x

。

【输出】

对于每组数据，输出序列的最大长度以及满足最大长度的序列的个数。

【输入样例】

【输出样例】

【提示】

数据范围与提示：

对于全部数据，1≤x≤220

。

如果我没有搞错的话，这道题应该算得上是结论题？挺简单的

序列长度就是该数的每一个质因子的次幂之和（稍微想想就能明白），而排列总数就是组合数学中的不全相异元素的排列。

#include<bits/stdc++.h>

using namespace std;

#define ll long long

const int N=;

ll n,jc[N+]={};

inline void solve(int x)

{

    ll ans=,cnt,k=;

    for(ll i=;i*i<=x;i++)

    {

        if(x%i==)

        {

            cnt=;

            while(x%i==)

            {

                cnt++;

                x/=i;

            }ans+=cnt;

        k*=jc[cnt];

        }

    }

    if(x>) ans++;

    printf("%lld %lld\n",ans,jc[ans]/k);

}

int main()

{

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

    jc[i]=jc[i-]*i;

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

    {

        solve(n);

    }

    return ;

}

巴特西

1628：X-factor Chain

1628：X-factor Chain

【题目描述】

【输入】

【输出】

【输入样例】

【输出样例】

【提示】

最新文章

热门文章