827.cpp

// 827 - 8402 (Simple version)
//
// 核心思路：
//   選定基底值 x，將所有數字依大小分配到合併層級：
//     Level k: 值在 [x*2^k, x*2^{k+1}-1] 的數 → 縮小到 x*2^k
//   每層可用數量 = 本層原生數量 + 下層合併進位 floor(c_{k-1}/2)
//   最終可達的最高層 L（c_L ≥ 1）→ 得分 = x * 2^L
//
// 為什麼不能只用 suffix sum？
//   因為值較大的數字在合併鏈中貢獻 > 1 個基底單位
//   例如 base=4 時，一個 8 等同於 2 個 4 的合併效果
//
// 時間複雜度：O(n + m * log(n))，因為每個 x 最多處理 log2(n) 層
// 空間複雜度：O(n + m)

#include <iostream>
using namespace std;

const int MAXN = 100005;

int arr[MAXN];
int freq[MAXN];
long long prefix[MAXN];

void generateArray(int* arr, int n, int m, int seed) {
    unsigned x = seed;
    for (int i = 1; i <= n; i++) {
        x ^= x << 13;
        x ^= x >> 17;
        x ^= x << 5;
        arr[i] = x % m + 1;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, seed;
    cin >> n >> m >> seed;

    generateArray(arr, n, m, seed);

    for (int i = 1; i <= n; i++) {
        freq[arr[i]]++;
    }

    // prefix[v] = freq[1] + freq[2] + ... + freq[v]
    // 用於 O(1) 查詢任意區間 [a, b] 的數字個數
    for (int i = 1; i <= m; i++) {
        prefix[i] = prefix[i - 1] + freq[i];
    }

    long long ans = 0;

    // 枚舉所有可能的基底值 x
    for (int x = 1; x <= m; x++) {
        long long carry = 0;

        for (int k = 0; ; k++) {
            long long lo = (long long)x << k;   // x * 2^k = 本層的值
            if (lo > m && carry == 0) break;

            // 本層原生數量：原始值在 [lo, lo*2-1] ∩ [1, m] 的數字
            long long native_k = 0;
            if (lo <= m) {
                long long hi = min((long long)m, lo * 2 - 1);
                native_k = prefix[hi] - prefix[lo - 1];
            }

            long long c = native_k + carry;
            if (c >= 1) {
                ans = max(ans, lo);   // 可達此層，得分 = x * 2^k
            }
            carry = c / 2;           // 進位到下一層
        }
    }

    cout << ans << "\n";

    return 0;
}