POJ 2409 Let it Bead 题解《挑战程序设计竞赛》

POJ 2409 Let it Bead 

乞巧珠：喜迎佳节，公司决定生产一种独一无二的节日限定手镯卖给单身狗们。这种独特的手镯由c色共s个珠子串成，无论是旋转还是翻转都不会与别人相同，蕴含着single、unique的美好祝愿。老板将手镯的设计任务交给还在加班的你，问一共可以设计多少种手镯？

4.1更加复杂的数学问题 

计数 

依然是是裸的Pólya定理，将《POJ 1286 Necklace of Beads》的代码改一改，就直接过了。

#include <iostream>
#include <map>
#include <vector>
using namespace std;

#define LL long long

inline LL power(LL p, LL n)
{
	LL sum = 1;
	while (n)
	{
		if (n & 1)
			sum *= p;
		p *= p;
		n /= 2;
	}
	return sum;
}

//************************************
// 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;
}

LL polya(const int& m, const int& n)
{
	map<int, int> primes = prime_factor(n);
	vector<int> divs = divisor(n);
	LL res = 0;
	for (int i = 0; i < divs.size(); ++i)
	{
		// 求divs[i]的欧拉函数值
		LL euler = divs[i];
		for (map<int, int>::iterator it = primes.begin(); it != primes.end(); ++it)
		{
			int p = it->first;
			if (divs[i] % p == 0) euler = euler / p * (p - 1);
		}

		res += euler * power(m, n / divs[i]);
	}

	// 最后除以n
	res /= n;
	return res;
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int c, s;
	while (~scanf("%d%d", &c, &s) && c && s)
	{
		if (s == 0)
		{
			puts("0");
			continue;
		}

		LL count = polya(c, s) * s;
		if (s & 1)
			count += s * power(c, s / 2 + 1);
		else
			count += (power(c, s / 2 + 1) + power(c, s / 2)) * (s / 2);
		count /= 2 * s;
		printf("%lld\n", count);
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

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