結果

問題 No.577 Prime Powerful Numbers
コンテスト
ユーザー ats5515
提出日時 2017-10-14 00:11:12
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 3,287 bytes
コンパイル時間 829 ms
コンパイル使用メモリ 83,852 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-17 18:22:56
合計ジャッジ時間 4,012 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 4 WA * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
#define int long long
//int MOD = 1000000007;
int modpow(int b,int e,int m) {
	int result = 1;
	while (e > 0) {
		if ((e & 1) == 1) {
			result = (result * b) % m;
		}
		e /= 2;
		b = (b * b) % m;
	}
	return result;
}
int powi(int a,int b) {
	if (b == 0) {
		return 1;
	}
	int res = powi(a, b / 2);
	if (b % 2 == 0) {
		return res*res;
	}
	else {
		return res*res*a;
	}
}
//	ユークリッドの互除法
int euclid(int m, int n) {
	if (m < n) { std::swap(m, n); }
	while (n != 0) {
		int temp = m;
		m = n;
		n = temp % n;
	}
	return m;
}

//	a = 2 として素数判定を行う
bool isPrime(int p, int a = 2) {
	if (p == 2) { return true; }								//	2は素数
	if (p < 2 || !(p & 1)) { return false; }	//	2よりも小さいまたは（2以外の）偶数なら計算するまでもなし
	return modpow(a, p - 1, p) == 1;
}

//	a を 2 以上の整数として k 回素数判定を行う。
bool isPrimeRange(int p, int k) {
	for (int count = 0, a = 2; count != k; ++count) {
		if (!isPrime(p, a)) { return false; }
		// ユークリッドの互除法を利用して p と a の最大公約数が 1であるかチェック
		while (euclid(p, ++a) != 1) {}
	}
	return true;
}

//	ミラーラビン法による確率的な素数判定
bool isPrimeMillerRabin(int p, int k) {
	if (p == 2) { return true; }								//	2は素数
	if (p < 2 || (p % 2 == 0)) { return false; }	//	2よりも小さいまたは（2以外の）偶数なら計算するまでもなし
	//srand((unsigned)time(NULL));

	//	p - 1 = pow( 2, s ) * d, s > 0 において、最初の奇数dを見つける。
	int d = p - 1;
	while (!(d & 1)) {
		d /= 2;
	}

	for (int n = 0; n != k; ++n) {
		int a = std::rand() % (p - 2) + 1;
		int t = d;
		int y = modpow(a, t, p);
		while (t != p - 1 && y != 1 && y != p - 1) {
			//cerr << t << endl;
			y = modpow(y, 2, p);
			t *= 2;
		}
		if (y != p - 1 && !(t & 1)) {
			return false;
		}
	}
	return true;
}

signed main() {
	//cerr << isPrimeMillerRabin(129, 50) << endl;
	cin.tie(0);
	ios::sync_with_stdio(false);
	int T;
	cin >> T;
	//T = 200;
	//cerr << (int)pow((int)powi(999, 6), 1/(double)1) << endl;
	string res;
	int m;
	int x;
	int aa;
	while (T--) {
		int N;
		cin >> N;
		//N = powi(MOD, 2) + powi(2, 1);
		//cerr << N << endl;
		//N = MOD;
		if (N % 2 == 0) {
			if (N == 2) {
				res = "No";
			}
			else {
				res = "Yes";
			}
		}
		else {
			m = 2;
			res = "No";
			while (N - m > 1 && m > 1) {
				x = 1;
				while (x < 60)
				{
					if (x == 1) {
						aa = N - m;
					}
					else {
						aa = (int)(pow(N - m, 1 / (double)(x)));
					}
					//cerr << N - m << " " << x << " " << aa << endl;
					//if (aa <= 1)break;
					//cerr << aa << endl;
					for (int j = aa - 3; j < aa + 3; j++) {
						if (powi(j, x) == N - m) {
							//cerr << j << " " << x << " " << N - m << endl;
							if (isPrimeMillerRabin(j, 50000)) {
								//cerr << m << " " << x << endl;
								res = "Yes";
								break;
							}
						}
					}
					x++;
				}
				
				
				if (res == "Yes")break;
				m *= 2;
			}
		}
		cout << res << endl;
	}
	//cout << res << endl;
}
0