SRM400 Div2 Medium

500

pow 関数で計算すると誤差で死ぬ。

これを１発で通せる人は凄いと思う。

bool is_prime(lli n)
{
  if (n == 0 || n == 1) return false;
  for (lli i = 2; i * i <= n; ++i) {
    if (n % i == 0) return false;
  }
  return true;
}

class StrongPrimePower {
public:
  vector <int> baseAndExponent(string n)
  {
    lli m;
    istringstream iss(n);
    iss >> m;

    vector<int> v;

    for (int p = 2; p <= 60; ++p) {
      double a = pow(m, 1.0 / p);
      lli x = (int)floor(a + 0.5);
      lli b = 1;

      for (int i = 0; i < (int)p; ++i) {
        b *= x;
      }

      if (is_prime(x) && m == b) {
        v.push_back(x);
        v.push_back(p);
      }
    }
    return v;
  }
};