結果

問題 No.577 Prime Powerful Numbers
ユーザー kimiyukikimiyuki
提出日時 2017-10-13 22:51:14
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,423 bytes
コンパイル時間 906 ms
コンパイル使用メモリ 114,860 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-11-17 18:02:52
合計ジャッジ時間 5,725 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 11 ms
5,248 KB
testcase_01 AC 55 ms
5,248 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 AC 24 ms
5,248 KB
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 AC 2 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <random>
#include <cmath>
#include <vector>
#include <algorithm>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <tuple>
#include <unordered_set>
#include <unordered_map>
#include <functional>
#include <cassert>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_from(i, m, n) for (int i = (m); (i) < int(n); ++(i))
#define repeat_reverse(i, n) for (int i = (n)-1; (i) >= 0; --(i))
#define repeat_from_reverse(i, m, n) for (int i = (n)-1; (i) >= int(m); --(i))
#define whole(x) begin(x), end(x)
#define unittest_name_helper(counter) unittest_ ## counter
#define unittest_name(counter) unittest_name_helper(counter)
#define unittest __attribute__((constructor)) void unittest_name(__COUNTER__) ()
using ll = long long;
using namespace std;

template <typename UnaryPredicate>
ll binsearch(ll l, ll r, UnaryPredicate p) { // [l, r), p is monotone
    assert (l < r);
    -- l;
    while (r - l > 1) {
        ll m = (l + r) / 2;
        (p(m) ? r : l) = m;
    }
    return r; // = min { x in [l, r) | p(x) }, or r
}

ll powint(ll x, int y) {
    ll z = 1;
    for (ll i = 1; i <= y; i <<= 1) {
        if (y & i) z *= x;
        x *= x;
    }
    return z;
}
unittest {
    assert (powint(3, 5) == 243);
    assert (powint(7, 3) == 343);
}

ll iroot(ll n, int k) {
    ll y = binsearch(0, n + 1, [&](ll x) {
        if (n * 1.1 < pow(x, k)) return true;
        return n <= powint(x, k);
    });
    if (n < powint(y, k)) -- y;
    return y;
}
unittest {
    repeat_from (a, 2, 100) {
        repeat_from (b, 1, 4) {
            ll c = iroot(a, b);
            assert (powint(c, b) <= a);
            assert (a < powint(c + 1, b));
        }
    }
}

ll powmod(ll x, ll y, ll p) { // O(log y)
    assert (0 <= x and x < p);
    assert (0 <= y);
    ll z = 1;
    for (ll i = 1; i <= y; i <<= 1) {
        if (y & i) z = z * x % p;
        x = x * x % p;
    }
    return z;
}
template <class Generator>
bool is_prime(ll n, int iteration, Generator & gen) { // miller-rabin primality test, O(k log n)
    assert (0 <= n);
    if (n == 2) return true;
    if (n == 1 or n % 2 == 0) return false;
    const ll d = (n-1) >> __builtin_ctzll(n-1); // remove trailing zeros
    uniform_int_distribution<ll> dist(1, n-2); // [l, r]
    repeat (dummy, iteration) {
        ll a = dist(gen);
        ll t = d;
        ll y = powmod(a, t, n);
        while (t != n-1 and y != 1 and y != n-1) {
            y = y * y % n;
            t *= 2;
        }
        if (y != n-1 and t % 2 == 0) return false;
    }
    return true;
}
bool is_prime(ll n) {
    static default_random_engine engine = default_random_engine(random_device()());
    return is_prime(n, 20, engine);
}

bool solve(ll n) {
// fprintf(stderr, "n = %lld\n", n);
    if (n >= 2 and n % 2 == 0) return true;  // Goldbach's conjecture
    for (ll pa = 2; ; pa *= 2) {
        ll qb = n - pa;
        if (qb <= 1) break;
        repeat_from (b, 1, 64) {
            ll q = iroot(qb, b);
// fprintf(stderr, "qb = %lld, b = %d -> q = %lld\n", qb, b, q);
            if (qb == powint(q, b) and is_prime(q)) return true;
        }
    }
    return false;
}

int main() {
    int q; scanf("%d", &q);
    while (q --) {
        ll n; scanf("%lld", &n);
        bool result = solve(n);
        printf("%s\n", result ? "Yes" : "No");
// fprintf(stderr, "%s\n", result ? "Yes" : "No");
    }
    return 0;
}
0