詰めるの大変だった。こういうの 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 のコードを読んだ。発想としては
としてとりうる値は最大でも
程度である
ということ。よって、 を全探索すればよい。手順としては
を求める
が素数かどうかを判定し、素数でなければ捨てる。素数の場合は 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; } };