結果

問題 No.577 Prime Powerful Numbers
ユーザー kimiyuki
提出日時 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0