POJ 3421 X-factor Chains 题解 《挑战程序设计竞赛》

POJ 3421 X-factor Chains

因子链：将一个数X分解成从1到X的数列，前一个数可以整除后一个数，求最大链长和链的个数。

2.6 数学问题的解题窍门

素数

比如10的约数是2和5各一个，那么最大链长就是2，到底有几个链呢？其实就是质因子们的排列组合——∏(质因子个数的阶乘)/(每个质因子的个数的阶乘)。只要我把它们排好了，顺序乘起来就能得到一条独一无二的链。

下面的代码里有很多模板，其实只用了后两个，其它的懒得删了

#ifndef ONLINE_JUDGE
#pragma warning(disable : 4996)
#endif
#include <iostream>
#include <vector>
#include <numeric>
#include <map>
using namespace std;

typedef unsigned long long ULL;

//************************************
// Method:    divisor
// FullName:  divisor
// Access:    public 
// Returns:   vector<int> 约数
// Qualifier: 约数枚举
// Parameter: const int & n 目标数n
//************************************
vector<int> divisor(const int& n)
{
	vector<int> res;
	for (int i = 1; i * i <= n; ++i)
	{
		if (n % i == 0)
		{
			res.push_back(i);
			if (i != n / i)
			{
				res.push_back(n / i);
			}
		}
	}

	return res;
}

//************************************
// Method:    prime_factor
// FullName:  prime_factor
// Access:    public 
// Returns:   map<int, int>
// Qualifier: 整数分解
// Parameter: int n
//************************************
map<int, int> prime_factor(int n)
{
	map<int, int> res;
	for (int i = 2; i * i <= n; ++i)
	{
		while (n % i == 0)
		{
			++res[i];
			n /= i;
		}
	}
	if (n != 1)
	{
		res[n] = 1;
	}
	return res;
}

//************************************
// Method:    prime_factor_time
// FullName:  prime_factor_time
// Access:    public 
// Returns:   vector<int>
// Qualifier: 只求解整数分解的因子的幂
// Parameter: int n
//************************************
vector<int> prime_factor_time(int n)
{
	vector<int> res;
	for (int i = 2; i * i <= n; ++i)
	{
		int time = 0;
		while (n % i == 0)
		{
			++time;
			n /= i;
		}
		res.push_back(time);
	}
	if (n != 1)
	{
		res.push_back(1);
	}

	return res;
}

//************************************
// Method:    factor
// FullName:  factor
// Access:    public 
// Returns:   int
// Qualifier: 阶乘，n!
// Parameter: const int & n
//************************************
ULL factor(const int& n)
{
	ULL res = 1;
	for (int i = 1; i <= n; ++i)
	{
		res *= i;
	}
	return res;
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int X;
	while (cin >> X)
	{
		vector<int> f = prime_factor_time(X);
		int length = accumulate(f.begin(), f.end(), 0);	// 幂之和是长度
		ULL number = factor(length);					// 全排列
		for (vector<int>::const_iterator it = f.begin(); it != f.end(); ++it)
		{
			number /= factor(*it);						// 去重复
		}

		cout << length << ' ' << number << endl;
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 3421 X-factor Chains 题解 《挑战程序设计竞赛》