結果
問題 | No.577 Prime Powerful Numbers |
ユーザー | Kmcode1 |
提出日時 | 2017-10-13 22:48:46 |
言語 | C++11 (gcc 11.4.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,958 bytes |
コンパイル時間 | 1,519 ms |
コンパイル使用メモリ | 165,544 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-17 18:01:39 |
合計ジャッジ時間 | 2,322 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 8 ms
6,816 KB |
testcase_01 | WA | - |
testcase_02 | AC | 2 ms
6,816 KB |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | AC | 2 ms
6,816 KB |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:75:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 75 | scanf("%lld", &n); | ~~~~~^~~~~~~~~~~~
ソースコード
#include "bits/stdc++.h" using namespace std; int q; class Rho { long long int mult(long long int A, long long int B, long long int n) { if (B == 0LL) { return 0; } long long int u = mult(A, B >> 1LL, n); u <<= 1LL; if (u >= n)u %= n; if (B & 1LL)u += A; if (u >= n)u %= n; return u; } long long int f(long long int x, long long int mod) { x %= mod; x = mult(x, x, mod); x += 1; x %= mod; return x; } long long int gcd(long long int a, long long int b) { if (a > b)swap(a, b); while (a) { swap(a, b); a %= b; } return b; } public: long long int find(long long int n) { srand(time(NULL)); long long int x = f(rand() % n, n); long long int y = f(f(x, n), n); while (1) { long long int ab = x - y; if (ab < 0)ab = -ab; long long int gc = gcd(ab, n); if (gc == n)return -1LL; if (gc == 1LL) { x = f(x, n); y = f(f(y, n), n); continue; } return gc; } } }; Rho rrr; long long int sq(long long int w,int j) { if (j == 1) { return w; } if (j == 2) { return sqrt(w); } return 0; } long long int pp(long long int w, int j) { long long int r = 1; while (j--) { r *= w; } return r; } int main() { cin >> q; while (q--) { long long int n; scanf("%lld", &n); if (n <= 2) { puts("No"); continue; } if (n % 2 == 0LL) { puts("Yes"); continue; } long long int r = 2; bool ok = false; while (r <= n) { long long int rest = n - r; if (rest <= 1) { break; } for (int j = 1; j <= 20; j++) { long long int k = pow(rest, 1.0 / (double)(j)); if (pp(k, j) == rest) { for (long long int ff = 1; ff <= 10000 && ff*ff <= k; ff++) { if (k%ff == 0) { continue; } } long long int go=rrr.find(k); if (go == -1) { ok = true; break; } } } if (ok) { break; } r *= 2LL; } if (ok) { puts("Yes"); } else { puts("No"); } } return 0; }