結果

問題 No.576 E869120 and Rings
ユーザー Kmcode1Kmcode1
提出日時 2017-10-13 22:46:05
言語 C++11
(gcc 11.4.0)
結果
MLE  
実行時間 -
コード長 1,854 bytes
コンパイル時間 1,822 ms
コンパイル使用メモリ 165,368 KB
実行使用メモリ 823,664 KB
最終ジャッジ日時 2024-11-17 11:37:37
合計ジャッジ時間 41,699 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 MLE -
testcase_01 MLE -
testcase_02 MLE -
testcase_03 MLE -
testcase_04 TLE -
testcase_05 MLE -
testcase_06 MLE -
testcase_07 MLE -
testcase_08 TLE -
testcase_09 MLE -
testcase_10 TLE -
testcase_11 TLE -
testcase_12 MLE -
testcase_13 MLE -
testcase_14 WA -
testcase_15 TLE -
testcase_16 TLE -
testcase_17 MLE -
testcase_18 MLE -
testcase_19 TLE -
testcase_20 MLE -
testcase_21 MLE -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:69:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   69 |                 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;

long long int sq(long long int w,int j) {
	if (j == 1) {
		return w;
	}
	if (j == 2) {
		return sqrt(w);
	}
	return 0;
}

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 / (double)(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