POJ-1286 : Necklace of Beads

問題概要

3色のビーズを使って数珠が何通り作れるか求める問題。

解法

とりあえず反転を無視して回転対称だけ重複を取り除いた個数をx個とする。これは蟻本で紹介されてる問題そのもの。左右対称な個数をr個とすると、求める個数は(x - r) / 2 + rとなる。左右対称な個数は奇数の場合は簡単で、偶数の場合は対称軸にビーズが乗っている場合と乗っていない場合を考えてやれば解ける。

acceptされたコード

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

typedef long long int64;

const int MAX_N = 25;

int64 pow_binary(int64 x, int n){
	int64 ret = 1;
	for(;n;n>>=1, x = x * x)if(n&1){
		ret = ret * x;
	}
	return ret;
}

//xの約数を全て求める。結果はソートされていない。
//計算量O(sqrt(x))。

vector<int64> divisor(int64 x){
	vector<int64> ret;
	for(int64 i=1; i*i <= x; ++i)if(x%i == 0){
		ret.push_back(i);
		if(i*i!=x){
			ret.push_back(x/i);
		}
	}
	return ret;
}

const int MAX_PHI = ::MAX_N;
int phi[MAX_PHI + 1];

//phi(n)のテーブルを作る。計算量O(MAX_PHI)よりちょっと重い。
void euler_phi_lookup(){
	for(int i=0; i<=MAX_PHI; ++i){
		phi[i] = i;
	}
	for(int i=2; i<=MAX_PHI; ++i)if(phi[i] == i){
		for(int j=i; j<=MAX_PHI; j+=i){
			phi[j] = phi[j] / i * (i - 1);
		}
	}
}

//xを素因数分解した結果を返す。
//計算量O(sqrt(x))。

map<int64, int> factorize(int64 x){
	map<int64, int> ret;
	for(int64 i=2; i*i <= x; ++i){
		for(;x%i == 0; ++ret[i], x/=i);
	}
	if(x != 1){
		++ret[x];
	}
	return ret;
}

int N;
bool visited[MAX_N + 1];
int64 memo[MAX_N + 1];

bool init(){
	return scanf("%d", &N), N!=-1;
}

int64 solve(){
	if(visited[N]){
		return memo[N];
	}
	visited[N] = true;

	if(N == 0){
		return memo[N] = 0;
	}

	int64 ans = 0;

	//反転無視
	map<int64, int> primes = factorize(N);
	vector<int64> divs = divisor(N);

	for(int i=0; i<(int)divs.size(); ++i){
		ans += phi[divs[i]] * pow_binary(3, N / divs[i]);
	}
	ans /= N;

	//左右対称なものを数える
	int64 rev = 0;
	rev += pow_binary(3, (N + 1) / 2);
	if(N % 2 == 0){
		rev += 3 * pow_binary(3, N / 2 - 1);
	}

	ans = (ans - rev) / 2 + rev;
	return memo[N] = ans;
}

int main(){
	euler_phi_lookup();
	for(;init();){
		printf("%lld\n", solve());
	}

	return 0;
}