放牧代码和思想
专注自然语言处理、机器学习算法

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 题解 《挑战程序设计竞赛》

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机