結果
問題 | No.577 Prime Powerful Numbers |
ユーザー |
|
提出日時 | 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); | ~~~~~^~~~~~~~~~~~
ソースコード
#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 monotoneassert (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 zerosuniform_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 conjecturefor (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;}