SRM628 div1 easy DivisorsPower

概要

d(n) = (nの正の約数の個数)、h(n) = n^d(n)とする。x = h^-1(n) を求めろ。複数存在する場合は最も小さいものを求めろ。

解法

d(x) として使われうる値は20程度までしか存在しない。d(x)を決め打って、そのd(x)のときh^-1(n)が存在するか考える。nのm乗根を求めたあとd(nのm乗根) == mであるかどうか判定すればよい。nのm乗根は二分探索を用いてO(mlogn)、d(n)はO(sqrt(sqrt(n)))で計算できる。全体で O( max(d(x))(mlogn + sqrt(sqrt(n))) ) で計算できる。
オーバーフローに注意

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

//二分累乗法 xのe乗
ll binpow(ll x, ll e) {
  ll a = 1, p = x;
  while(e > 0) {
    if(e%2 == 0) {p = (p*p); e /= 2;}
    else {a = (a*p); e--;}
  }
  return a;
}

// nのm乗根 整数でなければ-1 O(mlogn)
ll root(ll n, ll m) {
  ll lb = 1, ub = n;
  while(ub-lb > 1) {
    ll mid = (lb+ub)/2, tmp = mid, prev = 1;
    REP(i, m-1) {
      if(tmp/prev != (tmp*mid)/tmp) {tmp = n+1; break;}
      prev = tmp;
      tmp *= mid;
    }
    if(tmp >= n) ub = mid;
    else lb = mid;
  }
  ll tmp = ub, prev = 1;
  REP(i, m-1) {
    if(tmp/prev != (tmp*ub)/tmp) {tmp = -1; break;}
    prev = tmp;
    tmp *= ub;
  }
  if(tmp == n) return ub;
  return -1;
}

class DivisorsPower {
   public:
   long long findArgument(long long n)
  {
    ll ret = INF;
    FOR(i, 2, 21) {
      ll sq = root(n, i);
      if(sq == -1) continue;
      // d(sq) = i であれば
      ll cnt = 0;
      for(ll k=1; k*k<=sq; ++k) {
        if(sq%k==0) {
          cnt++;
          if(k*k!=sq) {
            cnt++;
          }
        }
      }
      if(cnt == i) chmin(ret, sq);
    }
    return ret==INF ? -1 : ret;
  }
};