結果

問題 No.2724 Coprime Game 1
コンテスト
ユーザー 回転
提出日時 2025-10-23 18:59:18
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,516 ms / 2,000 ms
コード長 4,354 bytes
コンパイル時間 1,252 ms
コンパイル使用メモリ 112,924 KB
実行使用メモリ 194,452 KB
最終ジャッジ日時 2025-10-23 18:59:34
合計ジャッジ時間 15,414 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

// 間に合うかテスト

#include <iostream>
#include <vector>
#include <numeric>      // std::iota (今回は使いませんが、UFの実装で役立つことがある)
#include <algorithm>    // std::swap
#include <map>          // Pythonのdefaultdictの代わりに使えます (今回は不要)

/**
 * @brief Union-Find (Disjoint Set Union) データ構造
 * * 経路圧縮とサイズによるマージを実装しています。
 */
struct UnionFind {
    std::vector<int> parents;

    /**
     * @brief n個の要素で初期化します。
     * @param n 要素数
     */
    UnionFind(int n) : parents(n, -1) {}

    /**
     * @brief 要素xの根を見つけます（経路圧縮付き）。
     * @param x 見つける要素
     * @return int 要素xの根
     */
    int find(int x) {
        if (parents[x] < 0) {
            return x;
        } else {
            // 経路圧縮
            return parents[x] = find(parents[x]);
        }
    }

    /**
     * @brief 要素xと要素yが含まれるグループを併合します。
     * @param x 
     * @param y 
     * @return bool 併合が実行された場合はtrue、既に同じグループだった場合はfalse
     */
    bool unite(int x, int y) {
        x = find(x);
        y = find(y);

        if (x == y) {
            return false;
        }

        // union by size (parents[x] には負のサイズが格納されている)
        if (parents[x] > parents[y]) {
            std::swap(x, y);
        }

        parents[x] += parents[y];
        parents[y] = x;
        return true;
    }

    /**
     * @brief 要素xが含まれるグループのサイズを返します。
     * @param x 
     * @return int グループのサイズ
     */
    int size(int x) {
        return -parents[find(x)];
    }

    /**
     * @brief 要素xと要素yが同じグループに属するかを判定します。
     * @param x 
     * @param y 
     * @return bool 同じグループならtrue
     */
    bool same(int x, int y) {
        return find(x) == find(y);
    }
};

/**
 * @brief エラトステネスの篩
 * * n以下の素数を列挙します。
 * @param n 上限値 (nを含む)
 * @return std::vector<int> n以下の素数のリスト
 */
std::vector<int> sieve_of_eratosthenes(int n) {
    // n+1個のbool配列 (0からnまで)
    std::vector<bool> primes(n + 1, true);
    primes[0] = primes[1] = false; // 0と1は素数ではない

    // p * p が n を超えるまで探索
    for (long long p = 2; p * p <= n; ++p) {
        if (primes[p]) {
            // pの倍数を篩い落とす (p*pから開始)
            for (long long i = p * p; i <= n; i += p) {
                primes[i] = false;
            }
        }
    }

    std::vector<int> prime_numbers;
    for (int p = 2; p <= n; ++p) {
        if (primes[p]) {
            prime_numbers.push_back(p);
        }
    }
    return prime_numbers;
}

int main() {
    // C++の標準入出力の高速化
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    const int MAX = 3 * 1000 * 1000 + 1;

    // MAXまでの素数を計算
    std::vector<int> ps = sieve_of_eratosthenes(MAX);

    // f[i] = iの素因数のリスト
    std::vector<std::vector<int>> f(MAX);
    for (int i : ps) {
        // iの倍数 j (j < MAX) に対して、f[j] に i を追加
        // オーバーフローを避けるため long long を使用
        for (long long now = i; now < MAX; now += i) {
            f[static_cast<int>(now)].push_back(i);
        }
    }

    // ans[i] = i とその素因数を連結したときのグループサイズ
    std::vector<int> ans(MAX, 0); // 0で初期化
    UnionFind uf(MAX);

    for (int i = 2; i < MAX; ++i) {
        for (int j : f[i]) {
            // i と iの素因数 j を連結
            uf.unite(i, j);
        }
        // iが属するグループのサイズを格納
        ans[i] = uf.size(i);
    }

    int T;
    std::cin >> T;
    for (int _ = 0; _ < T; ++_) {
        int N;
        std::cin >> N;
        
        // ans[N] の偶奇で判定
        if (ans[N] % 2 == 1) {
            std::cout << "P\n";
        } else {
            std::cout << "K\n";
        }
        // 三項演算子でも可
        // std::cout << (ans[N] % 2 == 1 ? "P" : "K") << "\n";
    }

    return 0;
}
0