一本通1628X-factor Chain

1628：X-factor Chain

时间限制: 1000 ms 内存限制: 524288 KB

【题目描述】

原题来自 POJ 3421

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

【输入】

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

【输出】

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

【输入样例】

【输出样例】

【提示】

数据范围与提示：

对于全部数据，1≤x≤2²⁰。

sol：看上去难系列

稍微想一下，发现是个排列组合一样的东西，又因为因数最多20，20!都没爆long long，随便搞搞

对于第 i 个质因数有G[i] 个，一共有cnt个质因数

　　　　　　　　　 cnt

序列的最大长度Len就是 ∑ G[i]

　　　　　　　　　i=1

　　　　　　　　 cnt

方案数就是Len！ / ∏ G[i]！

　　　　　　　　 i=1

代码实现复杂度接近于0。。。。

Ps：吐槽这里的sigma好难用啊qaq

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

inline ll read()

{

    ll s=;

    bool f=;

    char ch=' ';

    while(!isdigit(ch))

    {

        f|=(ch=='-'); ch=getchar();

    }

    while(isdigit(ch))

    {

        s=(s<<)+(s<<)+(ch^); ch=getchar();

    }

    return (f)?(-s):(s);

}

#define R(x) x=read()

inline void write(ll x)

{

    if(x<)

    {

        putchar('-'); x=-x;

    }

    if(x<)

    {

        putchar(x+''); return;

    }

    write(x/);

    putchar((x%)+'');

    return;

}

#define W(x) write(x),putchar(' ')

#define Wl(x) write(x),putchar('\n')

const int N=;

ll n;

ll Ges[N];

int main()

{

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

    {

        ll i,nn=n,ans1=,ans2=;

        *Ges=;

        for(i=;i<=sqrt(nn);i++) if(nn%i==)

        {

            ll tmp=;

            Ges[++*Ges]=;

            while(nn%i==)

            {

                nn/=i;

                tmp*=(++Ges[*Ges]);

                ans2*=(++ans1);

            }

            ans2/=tmp;

        }

        if(nn>)

        {

            Ges[++*Ges]=; ans1++; ans2*=ans1;

        }

        W(ans1); Wl(ans2);

    }

    return ;

}

巴特西