結果
| 問題 | No.577 Prime Powerful Numbers |
| ユーザー |
 Kmcode1
|
| 提出日時 | 2017-10-13 23:21:03 |
| 言語 | C++11 (gcc 11.4.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 5,548 bytes |
| コンパイル時間 | 1,624 ms |
| コンパイル使用メモリ | 179,192 KB |
| 実行使用メモリ | 21,900 KB |
| 最終ジャッジ日時 | 2024-11-17 18:12:38 |
| 合計ジャッジ時間 | 5,495 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 73 ms
21,892 KB |
| testcase_01 | AC | 81 ms
21,772 KB |
| testcase_02 | AC | 70 ms
21,888 KB |
| testcase_03 | WA | - |
| testcase_04 | AC | 72 ms
21,768 KB |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | AC | 71 ms
21,768 KB |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:231:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
231 | 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;
bool ok(long long int val, int j) {
long long int r = 1;
while (j--) {
r *= val;
if (r > val) {
return false;
}
}
if (r > val) {
return false;
}
return true;
}
long long int sq(long long int w,int j) {
if (j == 1) {
return w;
}
if (j == 2) {
return sqrt(w);
}
return -1;
}
long long int pp(long long int w, int j) {
long long int r = 1;
while (j--) {
r *= w;
}
return r;
}
vector<int> primes;
vector<int> smallestPrimeFactor;
void linearSieve(int n) {
if (n < 1) n = 1;
if ((int)smallestPrimeFactor.size() >= n + 1) return;
int primePiBound = n < 20 ? n - 1 : (int)(n / (log(n * 1.) - 2) + 2);
primes.assign(primePiBound + 1, numeric_limits<int>::max());
int P = 0;
smallestPrimeFactor.assign(n + 1, 0);
smallestPrimeFactor[1] = 1;
int n2 = n / 2, n3 = n / 3, n5 = n / 5;
if (n >= 2)
primes[P++] = 2;
if (n >= 3)
primes[P++] = 3;
for (int q = 2; q <= n; q += 2)
smallestPrimeFactor[q] = 2;
for (int q = 3; q <= n; q += 6)
smallestPrimeFactor[q] = 3;
for (int q = 5; q <= n5; q += 2) {
if (smallestPrimeFactor[q] == 0)
primes[P++] = smallestPrimeFactor[q] = q;
int bound = smallestPrimeFactor[q];
for (int i = 2; ; ++i) {
int p = primes[i];
if (p > bound) break;
int pq = p * q;
if (pq > n) break;
smallestPrimeFactor[pq] = p;
}
}
for (int q = (n5 + 1) | 1; q <= n; q += 2) {
if (smallestPrimeFactor[q] == 0)
primes[P++] = smallestPrimeFactor[q] = q;
}
primes.resize(P);
}
typedef int FactorsInt;
typedef vector<pair<FactorsInt, int> > Factors;
void primeFactors(FactorsInt x, Factors &out_v) {
linearSieve(x);
out_v.clear();
while (x != 1) {
int p = smallestPrimeFactor[x], k = 0;
x /= p, k++;
while (x % p == 0) x /= p, k++;
out_v.push_back(make_pair(p, k));
}
}
void divisors(int num, vector<FactorsInt> &v) {
Factors pf; primeFactors(num, pf);
queue<pair<int, int> > stk;
stk.push(make_pair(1, 0));
while (!stk.empty()) {
pair<int, int> f = stk.front();
stk.pop();
if (f.second == pf.size()) {
continue;
}
int cur = f.first;
stk.push(make_pair(f.first, f.second + 1));
for (int i = 1; i <= pf[f.second].second; i++) {
cur *= pf[f.second].first;
v.push_back(cur);
stk.push(make_pair(cur, f.second + 1));
}
}
v.push_back(1);
}
unordered_set<long long int> s;
bool pr[1000002];
bool isprime(long long int val) {
for (int i = 0; i < primes.size() && primes[i] * primes[i] <= val; i++) {
if (val%primes[i] == 0) {
return false;
}
}
return true;
}
struct Miller {
const vector<long long> v = { 2 , 7 , 61 }; // < 4,759,123,141
// x^k (mod m)
long long modpow(long long x, long long k, long long m) {
long long res = 1;
while (k) {
if (k & 1) {
res = res * x % m;
}
k /= 2;
x = x * x % m;
}
return res;
}
// check if n is prime
bool check(long long n) {
if (n < 2) {
return false;
}
long long d = n - 1;
long long s = 0;
while (d % 2 == 0) {
d /= 2;
s++;
}
for (long long a : v) {
if (a == n) {
return true;
}
if (modpow(a, d, n) != 1) {
bool ok = true;
for (long long r = 0; r < s; r++) {
if (modpow(a, d * (1LL << r), n) == n - 1) {
ok = false;
break;
}
}
if (ok) {
return false;
}
}
}
return true;
}
};
Miller miller;
int main() {
linearSieve(1000002);
for (int i = 0; i < primes.size(); i++) {
pr[primes[i]] = true;
long long int val = 1;
while (val <= 1000000000000000000LL) {
s.insert(val);
long long int pp2 = val;
val *= primes[i];
if (val / primes[i] != pp2) {
break;
}
}
}
s.erase(1);
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&&r>=0) {
long long int rest = n - r;
if (rest <= 1) {
break;
}
if (s.count(rest)) {
ok = true;
break;
}
for (int j = 2; j >= 1; j--) {
long long int k = sq(rest, j);
if (k <= 1)continue;
if (pp(k, j) == rest) {
j = 0;
if (k <= 1000000 && pr[k]) {
ok = true;
break;
}
else {
if (k <= 1000000 && pr[k] == false) {
continue;
}
}
if (isprime(k)==false) {
continue;
}
if (k <= 1000000000000LL) {
ok = true;
break;
}
if (miller.check(k)) {
ok = true;
break;
}
//return 1;
}
}
if (ok) {
break;
}
r *= 2LL;
}
if (ok) {
puts("Yes");
}
else {
puts("No");
}
}
return 0;
}