結果

問題 No.577 Prime Powerful Numbers
ユーザー Kmcode1Kmcode1
提出日時 2017-10-13 22:41:13
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,723 bytes
コンパイル時間 1,395 ms
コンパイル使用メモリ 151,176 KB
実行使用メモリ 4,388 KB
最終ジャッジ日時 2023-08-11 04:49:51
合計ジャッジ時間 2,703 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 12 ms
4,376 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 AC 278 ms
4,380 KB
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;


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 / j);
				if (pow(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;
}
0