問題概要
関数 を の正の約数の個数を求める関数であるとする。また、関数 を
と定める。
整数 が与えられる。 となる最小の を求めよ。そのような が存在しない場合は -1 で示せ。
解法
まず、 の計算は、試し割りによる素数判定や素因数分解と同様の手法で 時間で計算できることを確認しておきます。
さて、満たさなければならない等式の左辺を展開すると です。 の値を全通り試すことで解けそうに見えますが、 が素数の二乗だった場合 の値は まで有り得るので、これだけでは TLE してしまいます。
ところで、指数を 3 以上に限定できれば の値は 以下になります。各 の候補に対して 時間かけると結局危ないので、 に対する指数に関しても Brute Force して、冪乗が になるものだけ計算するようにすると間に合うようになります。指数が 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; } };