結果
問題 | No.577 Prime Powerful Numbers |
ユーザー |
|
提出日時 | 2017-10-13 22:56:31 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 669 ms / 2,000 ms |
コード長 | 2,668 bytes |
コンパイル時間 | 897 ms |
コンパイル使用メモリ | 78,912 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-17 18:04:22 |
合計ジャッジ時間 | 3,299 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 10 |
ソースコード
#include <iostream>#include <algorithm>#include <vector>#include <cmath>using namespace std;// n is even -> yes// n is odd -> p is even and q is oddconst int H = 32000;bool sieve[H];vector<long long> primes;using u64 = unsigned long long;bool is_prime(unsigned long long n) {using i64 = long long;using f80 = long double;if (n == 1) return false;if (n == 2) return true;if (n == 3) return true;if (n == 5) return true;if (n % 2 == 0) return false;if (n % 3 == 0) return false;if (n % 5 == 0) return false;int e = 0;u64 s = n - 1;while (s % 2 == 0) {e++;s /= 2;}auto modmul = [](u64 a, u64 b, u64 m) -> u64 {a %= m;b %= m;if (a == 0 || b == 0) return 0;if (a == 1) return b;if (b == 1) return a;u64 ret = 0;while (b > 0) {if (b & 1) {ret += a;if (ret >= m) ret -= m;}a += a;if (a >= m) {a -= m;}b >>= 1;}return ret;};auto modpow = [modmul](u64 a, u64 b, u64 m) {u64 ret = 1;for (; b > 0; b >>= 1) {if (b & 1) ret = modmul(ret, a, m);a = modmul(a, a, m);}return ret;};auto check = [&](u64 a) {u64 x = modpow(a, s, n);if (x == 1) return true;for (int i = 0; i < e; i++) {if (x == n - 1) return true;x = modmul(x, x, n);}return false;};for (int i : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {if (n % i != 0 && !check(i)) return false;}return true;}bool is_square(long long n) {long long s = sqrt(n);return s * s == n;}bool is_cubed(long long n) {long long s = cbrt(n);return s * s * s == n;}long long mul(long long a, long long b) {if (a == 0) return 0;if (b == 0) return 0;if (a * b / b != a) return 1.1e18;return a * b;}bool judge(long long n) {if (n <= 3) return false;if (n % 2 == 0) return true;for (long long i = 2; n - i >= 3; i *= 2) {long long p = n - i;if (is_prime(p)) return true;if (is_square(p) && is_prime(sqrt(p))) return true;if (is_cubed(p) && is_prime(cbrt(p))) return true;for (long long q : primes) {for (long long t = q*q*q; t <= p; t = mul(t, q)) {if (t == p) return true;}}}return false;}int main() {fill(sieve, sieve + H, true);sieve[0] = sieve[1] = false;for (int i = 2; i < H; i++) {if (sieve[i]) {primes.push_back(i);for (int j = i * 2; j < H; j += i) {sieve[j] = false;}}}int q;cin >> q;while (q--) {long long n;cin >> n;cout << (judge(n) ? "Yes" : "No") << endl;}}