TopCoder SRM 400 DIV1 Easy - StrongPrimePower (本番 268 人)

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

問題へのリンク

問題概要

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

制約

• 

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

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

• の場合は であることがわかるので、この範囲なら素数 を全探索できる
• の場合は を求め、以下を満たすかどうかを判定する
  • その二乗が に一致して
  • その値が素数である ( 程度の値なら素数判定可能)

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

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 のコードを読んだ。発想としては

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

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

1. を求める
2. が素数かどうかを判定し、素数でなければ捨てる。素数の場合は 3. に進む
3. を で割れるだけ割る。その回数が に一致すれば が答えである

という感じ。

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;
    }
};