結果

問題 No.577 Prime Powerful Numbers
ユーザー kimiyukikimiyuki
提出日時 2017-10-13 23:22:48
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 3,831 bytes
コンパイル時間 1,274 ms
コンパイル使用メモリ 113,048 KB
最終ジャッジ日時 2025-01-05 03:17:41
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 9 WA * 1
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:128:17: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  128 |     int q; scanf("%d", &q);
      |            ~~~~~^~~~~~~~~~
main.cpp:130:20: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  130 |         ll n; scanf("%lld", &n);
      |               ~~~~~^~~~~~~~~~~~

ソースコード

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