TopCoder SRM 599, Division 1, Level 1 : BigFatInteger

概要

整数 X があって、初期状態では X = 1 である。
X に対し、次の操作の内いずれかを任意の順番・回数適用することができる。

1. 任意の素数 p を選び、X を p 倍する
2. 任意の X の正の約数 d を選び、X を d 倍する

整数 A, B が与えられる。
X を にするために最小何回の操作が必要になるか求めよ。

解法

どちらの操作に於いても、p, d は の素因数です。
操作 1 は明らかに単一の素因数を乗じることしかできませんが、操作 2 に於いては（過去に乗じられた）素因数の積を乗じることができます。
操作 2 の方が目標達成に近づくので、できるだけ操作 2 を使った方が得になります。

では、操作 1 は最低何回必要でしょうか？
既に乗じられた素因数 p でもって p 倍する操作は操作 2 でも可能です。
しかし、新たな素因数を乗じることは操作 1 でしかできません。
つまり、素因数の種類分だけ、操作 1 が必要になります。

一つ以上含まれる素因数について、操作 2 を何回適用する必要があるかを考えます。
操作 1 は最初に適用した方がその後の自由度が高いので、既に 1 回乗じられた状態とします。
このとき、操作 2 で増やすことができる最大数は、既に乗じられた個数と等しくなり、すなわち個数を二倍にできます。
目標値を超えない範囲で逐次二倍して、最後に端数を調整するのが最適となります。

操作 2 は複数の素因数に対して同時・かつ独立に適用することができます。
従って、操作 2 を最も必要とする素因数での操作回数が、全体で必要な操作回数となります。

コード

typedef long long LL;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )

#define fst first
#define snd second

// 素因数分解 O( √N )
vector< long long > primeFactorization( long long N ); // 省略

class BigFatInteger
{
public:
	int minOperations( int A, int B )
	{
		vector<LL> factors = primeFactorization( A );
		map<LL,LL> counts;
		FOR( f, factors )
		{
			counts[f] += B;
		}

		int res = 0;
		FOR( p, counts )
		{
			if ( p.fst == 1 )
			{
				continue;
			}
			res = max( res, 63 - __builtin_clzll( p.snd ) + ( __builtin_popcountll( p.snd ) != 1 ) );
		}
		return counts.size() + res;		
	}
};