torus711 のアレ

主に競技プログラミングの問題について書きます

TopCoder SRM 628, Division 1, Level 1 : DivisorsPower

問題概要

 関数 d( n )n の正の約数の個数を求める関数であるとする。また、関数 h

  • h(n) = n^{ d(n) }

と定める。
 整数 n ( 2 \leq n \leq 10^{18} ) が与えられる。h(x) = n となる最小の x を求めよ。そのような x が存在しない場合は -1 で示せ。

解法

 まず、d(x) の計算は、試し割りによる素数判定や素因数分解と同様の手法で O( \sqrt n ) 時間で計算できることを確認しておきます。
 さて、満たさなければならない等式の左辺を展開すると x^{d(x)} = n です。x の値を全通り試すことで解けそうに見えますが、n素数の二乗だった場合 x の値は 10^9 まで有り得るので、これだけでは TLE してしまいます。
 ところで、指数を 3 以上に限定できれば x の値は \sqrt[3]{ 10^{18} } = 10^6 以下になります。各 x の候補に対して O( \sqrt x ) 時間かけると結局危ないので、x に対する指数に関しても Brute Force して、冪乗が n になるものだけ計算するようにすると間に合うようになります。指数が 2 の場合が残りますが、そのケースだけ予め試しておくことで、網羅的になります。

コード

using LL = long long;

template < typename T = int > using LIM = numeric_limits<T>;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

constexpr LL INF = LIM<LL>::max();

// x^n を mod で求める
// 反復二乗法
long long mod_pow( long long x, long long n, long long mod );

LL count_divisors( const LL x )
{
	LL res = 0;
	for ( LL i = 1; i * i <= x; ++i )
	{
		if ( !( x % i ) )
		{
			res += 1 + ( i * i != x );
		}
	}
	return res;
}

class DivisorsPower
{
public:
	long long findArgument(long long n)
	{
		{
			const LL sq = sqrt( n );

			REP( x, sq - 1, sq + 2 )
			{
				if ( LL( x ) * x == n && count_divisors( x ) == 2 )
				{
					return x;
				}
			}
		}

		REP( x, 1, 1000000 + 1 )
		{
			for ( int p = 1; p <= 64 && pow( x, p ) <= n + 1; ++p )
			{
				if ( mod_pow( x, p, INF ) == n && count_divisors( x ) == p )
				{
					return x;
				}
			}
		}

		return -1;
	}
};