加速版的 X因子链

涉及算法

1.线性筛法
2.预处理前缀和(在本题中是预处理阶乘)
3.多重集组合数

关于线性筛法

线性筛法是一种快速选出质数的算法
大致原理为 从2开始筛选素数 将每次筛选好的素数存储到primes 数组中然后将含有该素数因子的和数全部筛掉 用此算法的时间复杂度可以达到O(n);

下面是关于线性筛法的算法

int primes[N];//用于存放素数
int cnt;    //记录素数的个数 也作为primes数组的下标使用
bool st[N];//记录当前的数是否有被筛过

void get_primes(int n) //选出0-n中所有的素数
{
    for(int i=2;i<=n;i++)
    {
        if(st[i]==false)
        {
            st[i]=true;
            primes[cnt]=i;
            cnt++;
        }
        for(int j=0;i*primes[j]<=n;j++)
        {
            st[i*primes[j]]=true;
            if(i%primes[j]==0)
                break;
        }
    }
}

关于多重集组合数

可以理解为是高中数学排列组合的一个应用，应用场合是在排列是去除重复相同项排列的情况
公式为 n!(总排列的数目)/n1!n2!n3!....(每种组合内部的排列数)

为什么要预处理阶乘？

注意到该题最后是要算关于X的因子链序列的最大长度和个数
而关于X的因子链序列的计算便涉及到排列 这是因为不同因子交换顺序便会获得不同的序列
而在此过程中便会产生相同因子的排列情况 通过预处理阶乘便可快速获得阶乘数 
从而不需要在进行多余计算

以下为完整代码

#include<iostream>
#include<algorithm>
#include<cstdio>

using namespace std;

typedef long long LL;

const int N=(1<<20)+10;

LL f[20+10];    //用于存储阶乘和

int primes[N];//用于存放素数
int cnt;    //记录素数的个数 也作为primes数组的下标使用
bool st[N];//记录当前的数是否有被筛过
int minp[N];

void get_primes(int n) //选出0-n中所有的素数
{
    for(int i=2;i<n;i++)
    {
        if(st[i]==false)
        {
            st[i]=true;
            primes[cnt]=i;
            minp[i]=i;
            cnt++;
        }
        for(int j=0;i*primes[j]<=n;j++)
        {
            st[i*primes[j]]=true;
            minp[i*primes[j]]=primes[j];
            if(i%primes[j]==0)
                break;
        }
    }
}

int x;

int main()
{
    get_primes(N-1);    //由于本题是多个数据输入所以直接筛好所有素数

    f[0]=1;

    for(int i=1;i<=20;i++)
        f[i]=f[i-1]*i;

    while(scanf("%d",&x)!=-1)
    {
        LL sum=1;
        LL total=0; //记录X的因子数

        while (x>1)
        {   
            int p=minp[x];
            int k=0;    //记录每个因子的出现次数
            while(x%p==0)
            {
                k++;
                total++;
                x/=p;
            }
            sum*=f[k];
        }

        printf("%lld %lld\n",total,f[total]/sum);

    }
    return 0;
}