Pの競プロ記

競技プログラミングに関することを書きます。

StrongPrimePower (SRM400 div1 easy)

解法・感想など


nが入力で与えられたとき、n=p^qを満たすp、qを求める問題です。
nは10^18以下の自然数、pは素数です。

n <= 10^18であることから上式を満たす最大のqは59ということが分かります。
(p=2,q=60のとき、2^60 > 10^18 となる)
n=p^qを変形し、p=n^(1/q)とします。
qの範囲はすでに分かっているので、先ほど変形した式に代入しpを求めます。
そのときpの値は整数になるとは限らないのでここで四捨五入しておきます。(ここがポイントです)
pの値が整数かつ素数であるならn=p^qを満たします。

ちなみにround()を使うことで四捨五入することができます。

別解はqの範囲が分かっているのであとはそれぞれに対して二分探索をして解を求めることができます。そのときのp^qの値はとても大きくなるのでbigIntegerを用いています。無理やり感ハンパないです。


ソースコード


・想定解

class StrongPrimePower {
public:

  bool isPrime(int x) {
    if(x < 2) return false;
    if(x > 2 && x % 2 == 0) return false;
    for(int i = 3; i * i <= x; i += 2) {
        if(x % i == 0) return false;
    }
    return true;
  }

  vector <int> baseAndExponent(string _n) {
    vector<int> ans;

    lli n = 0;
    for(int i = 0; i < _n.size(); i++) {
      n = 10LL * n + (_n[i] - '0');
    }
    
    for(int q = 2; q <= 59; q++) {
      double tmp = pow(n, 1.0 / q);
      int p = round(tmp);
      if(!isPrime(p)) continue;
      lli v = 1;
      for(int i = 0; i < q; i++) v *= p;
      if(v == n) {
        ans.push_back(p);
        ans.push_back(q);
        break;
      }
    }
    return ans;
  }
};

・BigIntegerを用いて二分探索で無理やりやる解法

public class StrongPrimePower {
    
    public boolean isPrime(int x) {
        if(x < 2 || (x != 2 && x % 2 == 0)) return false;
        for(int i = 3; i * i <= x; i += 2) {
            if(x % i == 0) return false;
        }
        return true;
    }

    public int[] baseAndExponent(String _n) {
        int[] ans;

        BigInteger n = new BigInteger(_n);
        
        for(int q = 2; q <= 59; q++) {
            int l = 2;
            int r = 1000000000;
            while(r - l > 0) {
                int p = (l + r) / 2;
                BigInteger tmp = new BigInteger(Integer.valueOf(p).toString());
                tmp = tmp.pow(q);
                if(tmp.compareTo(n) == -1) l = p + 1;
                else if(tmp.compareTo(n) == 1) r = p;
                else {
                    if(isPrime(p)) {
                        ans = new int[]{p, q};
                        return ans;
                    }
                }
            }
        }
        return new int[]{};
    }
}