結果

問題 No.577 Prime Powerful Numbers
ユーザー koba-e964
提出日時 2017-10-13 23:24:09
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 1,363 ms / 2,000 ms
コード長 2,785 bytes
コンパイル時間 766 ms
コンパイル使用メモリ 95,028 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-17 18:13:12
合計ジャッジ時間 5,060 ms
ジャッジサーバーID
(参考情報)
judge2 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <algorithm>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>
#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
using namespace std;
typedef long long int ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> PI;
const ll inf = 5e18;
ll mulmod(ll x, ll y, ll mod) {
ll sum = 0;
ll cur = x % mod;
while (y > 0) {
if (y % 2 == 1) {
sum = (sum + cur) % mod;
}
cur = 2 * cur % mod;
y /= 2;
}
return sum;
}
ll powmod(ll a, ll e, ll mod) {
ll sum = 1;
ll cur = a % mod;
while (e > 0) {
if (e % 2) {
sum = mulmod(sum, cur, mod);
}
cur = mulmod(cur, cur, mod);
e /= 2;
}
return sum;
}
bool is_prime(ll x) {
if (x <= 1) { return false; }
if (x <= 3) { return true; }
if (x % 2 == 0) {
return false;
}
// From https://miller-rabin.appspot.com/
ll bases[7] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
int e = 0;
ll d = x - 1;
while (d % 2 == 0) {
e += 1;
d /= 2;
}
REP(i, 0, 7) {
if (bases[i] % x == 0) {
continue;
}
ll t = powmod(bases[i], d, x);
bool ok = true;
REP(j, 0, e) {
if (t == 1) { break; }
ll u = mulmod(t, t, x);
if (u == 1 && t != x - 1) {
ok = false;
break;
}
t = u;
}
ok &= t == 1;
if (not ok) {
return false;
}
}
return true;
}
ll pow_ll(ll x, int e) {
assert (e >= 1);
if (x <= 1) {
return x;
}
ll cur = 1;
ll lim = inf / x + 1;
REP(_, 0, e) {
if (cur >= lim) {
return inf;
}
cur *= x;
}
return cur;
}
ll exact_root(ll x, int e) {
if (e == 1) {
return x;
}
ll y = pow(x, 1.0 / e);
for (ll t = max(y - 10, 0LL); t <= y + 10; ++t) {
if (pow_ll(t, e) == x) {
return t;
}
}
return -1;
}
bool is_prime_power(ll x) {
assert (x < inf);
bool is_square = exact_root(x, 2) != -1;
for (int e = 1; e <= 45; e += is_square ? 1 : 2) {
ll y = exact_root(x, e);
if (y == -1) {
continue;
}
if (is_prime(y)) {
return true;
}
}
return false;
}
bool solve(ll n) {
if (n % 2 == 0) {
return n >= 4;
}
// n is odd
// n = 2^? + q^? (q >= 3)
REP(b, 1, 62) {
ll t = 1LL << b;
if (n <= t) {
break;
}
ll rest = n - t;
if (is_prime_power(rest)) {
return true;
}
}
return false;
}
int main(void) {
int q;
cin >> q;
while (q--) {
ll n;
cin >> n;
cout << (solve(n) ? "Yes" : "No") << endl;
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0