acwing1295. X的因子链

题目链接：1295. X的因子链 - AcWing题库

算法：数论+线性筛法求素数

x如果想要尽可能多的分为几个因子，那么就应该分成素数，因为如果是合数说明还能分。

题目要求求出①这段序列的最大长度和②最大长度序列的个数

 最大长度：

从当前数按照最小的质因数开始分解，如果大于一每次 /= 最小质因数，这样就可以得到最长的序列。

最大长度序列的个数：

假设最大长度为tot，那么假设tot个数内各不相同，全排列的组合数为 tot ！

但是内部其实有很多相同的数，我们要做的就是统计每个数出现的次数

所以刚好可以使用sum []来记录

因为在全排列中，这n个相同的数的排列数其实是等价的，所以只要 / n！

本题代码：

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

using namespace std;
typedef long long LL;

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

int cnt, primes[N];//cnt用来记录素数的下标 
bool st[N];//用来标记合数 
int minp[N];//最小质因数 

void get_primes(int n)
{
	for(int i = 2;i <= n;i ++ )//从2开始找数 
	{
		if(!st[i])//如果这个数没有被筛出去过，说明是一个质数 
		{
			primes[cnt ++ ] = i;
			minp[i] = i;//质数的最小质因数是自己本身 
		}
		for(int j = 0;primes[j] * i <= n;j ++ )//primes从小到大开始枚举 
		{
			int t = primes[j] * i;
			st[t] = true;//如果一个数能表示为两个数的积说明是合数 
			minp[t] = primes[j];//最小质因数是primes[j]，因为从小到大开始枚举的质数 
			if(i % primes[j] == 0) break;//最关键的一步，确保只会筛一次 
		}
	}
}

int main()
{
	int x;
	
	get_primes(N - 1);
	int sum[N];
	while(scanf("%d", &x) != -1)
	{
		int k = 0, tot = 0;
		while(x > 1)
		{
			int p = minp[x];
			sum[k] = 0;
			while(x % p == 0)
			{
				x /= p;
				sum[k] ++;
				tot ++;
			}
			k ++;
		}
		
		LL res = 1;
		for(int i = 1;i <= tot;i ++ ) res *= i;
		 
		for(int i = 0;i < k;i ++ )
			for(int j = 1;j <= sum[i];j ++ ) res /= j;
			
			printf("%d %lld\n", tot, res);
	}
	
	return 0;
}