結果

問題 No.577 Prime Powerful Numbers
ユーザー anta
提出日時 2017-10-13 22:54:29
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 31 ms / 2,000 ms
コード長 3,936 bytes
コンパイル時間 1,691 ms
コンパイル使用メモリ 178,100 KB
実行使用メモリ 8,932 KB
最終ジャッジ日時 2024-11-17 18:03:48
合計ジャッジ時間 2,605 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if (x < y) x = y; }


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);
}


inline long long mulmodll(long long a, long long b, long long m) {
	long long quot = (long long)((long double)a * b / m + 0.5);
	long long res = a * b - m * quot;
	res = a * b - m * quot;
	if (res < 0) res += m;
	return res;
}

long long powmodll(long long a, unsigned long long k, const long long MOD) {
	a %= MOD;
	long long r = MOD == 1 ? 0 : 1;
	while (k) {
		if (k & 1)
			r = mulmodll(r, a, MOD);
		a = mulmodll(a, a, MOD);
		k >>= 1;
	}
	return r;
}

bool suspect(ll a, int s, ll d, ll n) {
	auto x = powmodll(a, d, n);
	if (x == 1) return true;
	for (int r = 0; r < s; ++r) {
		if (x == n - 1) return true;
		x = mulmodll(x, x, n);
	}
	return false;
}

bool isPrime(ll n) {
	if (n <= 1 || (n > 2 && (n & 1) == 0)) return false;
	if (n < (ll)smallestPrimeFactor.size())
		return smallestPrimeFactor[(size_t)n] == n;
	const int test[] = { 2,3,5,7,11,13,17,19,23,-1 };
	auto d = n - 1;
	int s = 0;
	while (d % 2 == 0) ++s, d /= 2;
	for (int i = 0; test[i] < n && test[i] != -1; ++i)
		if (!suspect(test[i], s, d, n)) return false;
	return true;
}

int sqrti(long long x) {
	int s = (int)sqrt(x * 1.L);
	long long sqs = (long long)s * s;
	if (sqs > x) {
		do -- s; while ((long long)s * s > x);
	} else {
		while (sqs <= x - (2 * s + 1)) {
			sqs += 2 * s + 1;
			++ s;
		}
	}
	return s;
}

vector<ll> remainingPrimePowers;
bool isPrimePower(ll n) {
	if (n <= 0) return false;
	if ((n & (n - 1)) == 0) return true;
	if (isPrime(n)) return true;
	int sqrtn = sqrti(n);
	if ((ll)sqrtn * sqrtn == n && isPrime(sqrtn)) return true;
	if (remainingPrimePowers.empty()) {
		linearSieve(1000000);
		for (int p : primes) {
			if (p > (int)1e6) break;
			ll lim = (ll)1e18 / p;
			for (ll q = (ll)p * p * p; ; q *= p) {
				remainingPrimePowers.push_back(q);
				if (q > lim) break;
			}
		}
		sort(remainingPrimePowers.begin(), remainingPrimePowers.end());
	}
	return binary_search(remainingPrimePowers.begin(), remainingPrimePowers.end(), n);
}

int main() {
	int T;
	scanf("%d", &T);
	for (int ii = 0; ii < T; ++ ii) {
		long long N;
		scanf("%lld", &N);
		bool ans;
		if (N <= 2) {
			ans = false;
		} else if (N % 2 == 0) {
			ans = true;
		} else {
			ans = false;
			for (ll x = 2; x < N - 1; x *= 2) {
				ans |= isPrimePower(N - x);
			}
		}
		puts(ans ? "Yes" : "No");
	}
	return 0;
}
0