[ICPC] 백준 28152 - Power of Divisors

https://www.acmicpc.net/problem/28152

힌트 1

문제에서 유효한 해가 존재할 때 $f(n)$의 값은 충분히 작다.

힌트 2

$n^{f(n)} = x$라는 조건에 의해 $x$는 어떤 수의 거듭제곱으로 이루어져야만 함을 확인할 수 있다.

 

힌트 1과 힌트 2에서 언급한 사실을 종합했을 때, 후보를 빠르게 추릴 수 있는 방법이 있는가?

풀이

$2^{64} > 10^{18}$이므로, $f(n)$이 가질 수 있는 최댓값을 64로 잡는다.

 

그러면 1부터 64까지 반복을 돌면서 $1 \leq i \leq 64$에 대해 어떤 정수 $a$가 $a^{i} = x$인지 $a$에 대해 이진탐색을 시행하여 확인할 수 있다.

 

$a^{i} = x$를 만족하는 a를 찾을 경우, $f(a) = i$인지 $O(\sqrt a)$에 확인할 수 있다.

 

이렇게 해서 적절한 $a$를 찾거나, 없으면 -1을 출력하면 된다.

 

정답 코드 - C++

#pragma GCC target("fma,avx,avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
 
using namespace std;
using namespace __gnu_pbds;
 
using ll = int_fast64_t;
using pii = pair<int, int>;
// using oset = tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;
 
ll x;
 
void solve()
{
  cin >> x;
 
  if (x == 1)
  {
    cout << 1;
    return;
  }
 
  for (int i = 1; i <= 64; i++)
  {
    __int128_t lo = 1, hi = 1e9;
 
    ll good = -1;
    ll cand = -1;
    while (lo <= hi)
    {
      auto mid = lo + (hi - lo) / 2;
 
      __int128_t val = 1;
      for (int j = 0; j < i; j++)
      {
        val *= mid;
        if (val > x) break;
      }
 
      if (val == x)
      {
        good = mid;
        cand = mid;
        break;
      }
 
      if (val > x)
      {
        hi = mid - 1;
      }
      else
      {
        lo = mid + 1;
      }
    }
 
    if (good == -1) continue;
 
    map<int, int> mp;
 
    for (int i = 2; (ll)i * i <= good; i++)
    {
      if (good % i) continue;
      while (good % i == 0)
      {
        ++mp[i];
        good /= i;
      }
    }
 
    if (good != 1)
    {
      ++mp[good];
    }
 
 
    int cnt = 1;
 
    for (auto [k, v] : mp)
    {
      cnt *= (v + 1);
    }
 
    if (cnt == i)
    {
      cout << cand;
      return;
    }
  }
 
  cout << -1;
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}