結果

問題 No.577 Prime Powerful Numbers
ユーザー kimiyuki
提出日時 2017-10-13 22:48:04
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,914 bytes
コンパイル時間 1,332 ms
コンパイル使用メモリ 110,876 KB
最終ジャッジ日時 2025-01-05 03:13:42
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 3 WA * 7
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:121:17: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  121 |     int q; scanf("%d", &q);
      |            ~~~~~^~~~~~~~~~
main.cpp:123:20: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  123 |         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 <class T> inline void setmax(T & a, T const & b) { a = max(a, b); }
template <class T> inline void setmin(T & a, T const & b) { a = min(a, b); }
template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }
const int dy[] = { -1, 1, 0, 0 };
const int dx[] = { 0, 0, 1, -1 };
bool is_on_field(int y, int x, int h, int w) { return 0 <= y and y < h and 0 <= x and x < w; }

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;
}
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;
}

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));
        }
    }
}

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 (b, 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