結果

問題 No.577 Prime Powerful Numbers
ユーザー kimiyukikimiyuki
提出日時 2017-10-13 23:22:48
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 3,831 bytes
コンパイル時間 1,425 ms
コンパイル使用メモリ 113,128 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-08-11 04:59:36
合計ジャッジ時間 2,081 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
4,380 KB
testcase_01 WA -
testcase_02 AC 4 ms
4,380 KB
testcase_03 AC 25 ms
4,380 KB
testcase_04 AC 11 ms
4,380 KB
testcase_05 AC 91 ms
4,380 KB
testcase_06 AC 19 ms
4,376 KB
testcase_07 AC 106 ms
4,380 KB
testcase_08 AC 29 ms
4,380 KB
testcase_09 AC 35 ms
4,380 KB
testcase_10 AC 2 ms
4,376 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) {
// fprintf(stderr, "%lld %d\n", x, y);
    ll z = 1;
    for (ll i = 1; i <= y; i <<= 1) {
        if (y & i) z *= x;
        if ((i << 1) <= y) x *= x;
    }
    return z;
}
unittest {
    assert (powint(3, 5) == 243);
    assert (powint(7, 3) == 343);
}

ll iroot(ll n, int k) {
    if (k == 1) return n;
    double approx = pow(n, 1.0 / k);
    ll l = max<int>(0, approx - 1);
    ll r = min<int>(n, approx + 2) + 1;
    if (l >= r) return 0;
    ll y = binsearch(l, r, [&](ll x) {
        if (n * 1.0001 < 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));
        }
    }
}

typedef __int128 int128_t;
int128_t powmod(int128_t x, int128_t y, int128_t p) { // O(log y)
    assert (0 <= x and x < p);
    assert (0 <= y);
    int128_t z = 1;
    for (int128_t 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);
        int128_t t = d;
        int128_t 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) return false;
    if (n >= 4 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, 60 + 1) {
// fprintf(stderr, "iroot %lld %d\n", qb, b);
            ll q = iroot(qb, b);
// fprintf(stderr, "qb = %lld, b = %d -> q = %lld\n", qb, b, q);
// fprintf(stderr, "check\n");
            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