SRM628D1Easy DivisorsPower
ちょっと苦手
問題概要(原文)
$f(x) = x^h(x)$ とする．ここで $h(x)$ は $x$ の約数の数に等しい．
$f(x) = N$ を満たす $x$ であって最小の値を求めよ．
考察
$1$ は特殊ケースだが，あまり考えなくてもよいようになっている．
約数の数は $2$ 以上であるので，答えは少なくとも $\sqrt{N}$ 以下であることがわかる．
約数の数が $2$ 個となるケース $N=p^2$ となる場合であるので，そのような $p$ は二分探索で求められる．
約数の数が $3$ 個となるケースは $N=( p^{2} )^3$ となる場合だけであるので， $10^{6}$ 以下の整数全てについて調べればよい．
計算量は $\sum_{i = 1}^{M} d(i)$ ステップ程度の計算量で済む．
ソースコード
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
public class DivisorsPower
{
public long findArgument(long n)
{
var a = new int[1000050];
for (int i = 1; i < 1000050; i++)
{
for (int j = i; j < 1000050; j += i)
a[j] += 1;
}
for (int i = 1; i < 1000050; i++)
{
var k = a[i];
var v = n;
for (int j = 0; j < k; j++)
if (v % i == 0) v /= i;
else { v = -1; break; }
if (v == 1) return i;
}
long l = 1, r = 1000000001;
for (int i = 0; i < 50; i++)
{
var m = (l + r) / 2;
if (m * m >= n) r = m;
else l = m;
}
if (r * r == n)
{
for (long i = 2; i * i <= r; i++)
if (r % i == 0) r = -1;
if (r != -1) return r;
}
return -1;
}
}
コメント
- medより難しい
