結果

問題 No.2724 Coprime Game 1
ユーザー rieaaddlreiuurieaaddlreiuu
提出日時 2024-05-22 19:38:22
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 240 ms / 2,000 ms
コード長 891 bytes
コンパイル時間 1,684 ms
コンパイル使用メモリ 171,744 KB
実行使用メモリ 15,392 KB
最終ジャッジ日時 2024-05-22 19:38:26
合計ジャッジ時間 3,649 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 36 ms
15,308 KB
testcase_01 AC 36 ms
15,220 KB
testcase_02 AC 36 ms
15,324 KB
testcase_03 AC 198 ms
15,252 KB
testcase_04 AC 240 ms
15,392 KB
testcase_05 AC 214 ms
15,260 KB
testcase_06 AC 122 ms
15,244 KB
testcase_07 AC 203 ms
15,320 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;

vector<bool> Eratosthenes(int N) {
    vector<bool> isprime(N+1, true);
    isprime[0] = isprime[1] = false;
    for (int p = 2; p <= N; ++p) {
        if (!isprime[p]) continue;
        for (int q = p * 2; q <= N; q += p) {
            isprime[q] = false;
        }
    }
    return isprime;
}

int main(){
	int N_max = 3000000;
	vector<bool> is_prime = Eratosthenes(N_max);
	vector<int> prime_count(N_max+1);//prime_count[i] : i以下の素数の個数
	int count=0;
	for(int i=0;i<prime_count.size();i++){
		if(is_prime[i]){
			count++;
		}
		prime_count[i] = count;
	}
	int T;
	cin >> T;
	for(int i=0;i<T;i++){
		int N,S_size;
		cin >> N;
		if(is_prime[N]){
			cout << "P" << endl;
		} else {
			S_size = N-(1+prime_count[N]-prime_count[N/2]);
			if(S_size%2 == 1){
				cout << "P" << endl;
			} else {
				cout << "K" << endl;
			}
		}
	}
}
0