075.md

075 - Magic For Balls (★3)

解答

#include <iostream>
#include <vector>

// 素因数分解の結果を返す
// 例: GetPrimeFactors(36) = { 2, 2, 3, 3 }
std::vector<long long> GetPrimeFactors(long long n)
{
	std::vector<long long> factors;

	// 2～√N までの数で試し割り
	for (long long i = 2; (i * i) <= n; ++i)
	{
		while (n % i == 0)
		{
			factors.push_back(i);
			n /= i;
		}
	}

	if (n != 1LL)
	{
		factors.push_back(n);
	}

	return factors;
}

int main()
{
	// ボールに書かれた整数が N
	long long N;
	std::cin >> N;

	// 素因数の個数
	const auto count = GetPrimeFactors(N).size();

	// count 個の素因数に分解するには,
	// 少なくとも, (count <= 2^i) となる i 回の操作が必要になる
	//
	// 例:
	// count     | 必要な操作の最小回数
	//  1 個以下 | 0
	//  2 個以下 | 1
	//  4 個以下 | 2
	//  8 個以下 | 3
	// 16 個以下 | 4
	for (int i = 0;; ++i)
	{
		if (count <= (1ULL << i))
		{
			// 解答を出力
			std::cout << i << '\n';
			break;
		}
	}
}

補足: 最後の for は以下のコードに相当します。

	{
		if (count <= 1)
		{
			std::cout << 0 << '\n';
		}
		else if (count <= 2)
		{
			std::cout << 1 << '\n';
		}
		else if (count <= 4)
		{
			std::cout << 2 << '\n';
		}
		else if (count <= 8)
		{
			std::cout << 3 << '\n';
		}
		else if (count <= 16)
		{
			std::cout << 4 << '\n';
		}
		else if (count <= 32)
		{
			std::cout << 5 << '\n';
		}
		else if (count <= 64)
		{
			std::cout << 6 << '\n';
		}

		// ...
	}