けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

TopCoder SRM 400 D1E StrongPrimePower

詰めるの大変だった。こういうの 240pt で通せる人ってどうなってるの!?

問題へのリンク

問題概要

2 以上の整数  N が与えられる。 N が狭義の素数べき (素数  p と 2 以上の整数  q を用いて  p^{q} と書ける数) であるかどうかを判定し、素数べきの場合には  p, q の値を求めよ。

制約

  •  2 \le N \le 10^{18}

解法 1: q が 3 以上の場合と 2 の場合とで場合分け

 N がとにかく大きいので、 N素数かどうかを判定することさえできない。どうしたらよいのだろう...と思ったが

  •  q \ge 3 の場合は  p \le 10^{6} であることがわかるので、この範囲なら素数  p を全探索できる
  •  q = 2 の場合は  \lfloor \sqrt{N} \rfloor を求め、以下を満たすかどうかを判定する
    • その二乗が  N に一致して
    • その値が素数である ( 10^{9} 程度の値なら素数判定可能)

という感じで場合分けして解けることに気がついた。前者の  10^{6} 以下の素数の列挙には、エラトステネスの篩を用いた。

bool isprime(long long n) {
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p == 0) return false;
    }
    return true;
}

class StrongPrimePower {
public:
    vector <int> baseAndExponent(string sn) {
        vector <int> res;
        long long n; istringstream si(sn); si >> n;

        // エラトステネス
        vector<bool> isp(MAX, 1);
        isp[0] = isp[1] = false;
        for (long long p = 2; p < MAX; ++p) {
            if (!isp[p]) continue;
            for (long long i = p * 2; i < MAX; i += p) isp[i] = false;
        }

        // p^(3 以上) を探索
        for (long long p = 2; p * p * p <= n; ++p) {
            if (n % p != 0 || !isp[p]) continue;
            long long nn = n;
            int ex = 0;
            while (nn % p == 0) {
                nn /= p;
                ++ex;
            }
            if (nn == 1) {
                res.push_back(p);
                res.push_back(ex);
                return res;
            }
        }

        // p^2 を探索
        long long b = (long long)(sqrt(n) + 0.5);
        if (b * b == n && isprime(b)) {
            res.push_back(b);
            res.push_back(2);
            return res;
        }
        
        return res;
    }
};

解法 2: q を全探索

こっちの方が明快だったかもしれない。Petr のコードを読んだ。発想としては

  •  q としてとりうる値は最大でも  60 程度である

ということ。よって、 q を全探索すればよい。手順としては

  1.  p = \lfloor N^{\frac{1}{q}} \rfloor を求める
  2.  p素数かどうかを判定し、素数でなければ捨てる。素数の場合は 3. に進む
  3.  N p で割れるだけ割る。その回数が  q に一致すれば  p, q が答えである

という感じ。

bool isprime(long long n) {
    if (n <= 1) return false;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p == 0) return false;
    }
    return true;
}

class StrongPrimePower {
public:
    vector <int> baseAndExponent(string sn) {
        vector <int> res;
        long long n; istringstream si(sn); si >> n;

        for (int q = 2; q <= 65; ++q) {
            long long p = (long long)(pow(n, 1.0/q) + 0.5);
            if (!isprime(p)) continue;

            long long exp = 0;
            long long nn = n;
            while (nn % p == 0) ++exp, nn /= p;
            if (exp == q) {
                res.push_back(p);
                res.push_back(q);
                return res;
            }
        }
        return res;
    }
};