結果

問題 No.577 Prime Powerful Numbers
コンテスト
ユーザー Kmcode1
提出日時 2017-10-13 22:51:50
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 2,370 bytes
コンパイル時間 1,491 ms
コンパイル使用メモリ 168,368 KB
実行使用メモリ 17,096 KB
最終ジャッジ日時 2024-11-17 18:03:13
合計ジャッジ時間 20,723 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other AC * 2 WA * 2 TLE * 6
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:101:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  101 |                 scanf("%lld", &n);
      |                 ~~~~~^~~~~~~~~~~~

ソースコード

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;
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);
	}
	long long int mint = 0;
	long long int maxt = cbrt(w) + 2;
	while (mint + 1LL < maxt) {
		long long int mid = (mint + maxt) >> 1LL;
		if (ok(mid, j) == false) {
			maxt = mid;
		}
		else {
			mint = mid;
		}
	}
	if (ok(maxt, j)) {
		return maxt;
	}
	return mint;
}
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 = sq(rest, 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;
}
0