結果
問題 | No.2724 Coprime Game 1 |
ユーザー | 👑 ygussany |
提出日時 | 2024-03-30 12:24:00 |
言語 | C (gcc 12.3.0) |
結果 |
AC
|
実行時間 | 53 ms / 2,000 ms |
コード長 | 642 bytes |
コンパイル時間 | 184 ms |
コンパイル使用メモリ | 30,976 KB |
実行使用メモリ | 16,536 KB |
最終ジャッジ日時 | 2024-04-12 20:50:49 |
合計ジャッジ時間 | 1,214 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 30 ms
16,396 KB |
testcase_01 | AC | 28 ms
16,448 KB |
testcase_02 | AC | 29 ms
16,388 KB |
testcase_03 | AC | 43 ms
16,536 KB |
testcase_04 | AC | 50 ms
16,348 KB |
testcase_05 | AC | 53 ms
16,384 KB |
testcase_06 | AC | 41 ms
16,300 KB |
testcase_07 | AC | 48 ms
16,304 KB |
ソースコード
#include <stdio.h> int solve(int N) { int i, j, k; static char flag[3000001] = {}; static int num[3000001] = {}; if (num[2] == 0) { for (i = 2; i <= 3000000; i++) { if (flag[i] != 0) continue; for (j = i * 2; j <= 3000000; j += i) flag[j] = 1; } for (i = 3, num[2] = 1; i <= 3000000; i++) { num[i] = num[i-1]; if (flag[i] == 0) num[i]++; } } if (flag[N] == 0) return 0; else if ((N - 2 - (num[N] - num[N/2])) % 2 == 0) return 0; else return 1; } int main() { int T, N; scanf("%d", &T); while (T--) { scanf("%d", &N); if (solve(N) != 0) printf("K\n"); else printf("P\n"); } fflush(stdout); return 0; }