結果

問題 No.2724 Coprime Game 1
ユーザー rieaaddlreiuu
提出日時 2024-05-22 19:38:22
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 227 ms / 2,000 ms
コード長 891 bytes
コンパイル時間 1,727 ms
コンパイル使用メモリ 170,444 KB
実行使用メモリ 15,464 KB
最終ジャッジ日時 2024-12-20 18:32:29
合計ジャッジ時間 3,544 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

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