考点：随机化/生日悖论。

设 b_i=f(i)，由于 a 是随机序列，f 运算没有破坏随机性，故可以认为 b 也是随机序列。

策略：不断枚举 x 并计算 f(x)，若发现相同的就马上输出。可以证明能够很快找出相同。

引理：生日悖论：一年有 n 天，有 k 人，生日均匀分布且相互独立。问两人生日相同的概率达到 p_0 至少要多少个人。

设生日互不相同，显然概率为 p=\dfrac{n}n\times\dfrac{n-1}n\times\cdots\times\dfrac{n-k+1}n，则有 1-p\ge p_0,p\le 1-p_0。根据 1+x\le e^x 有 p\le e^{-\frac1n}\times e^{-\frac2n}\times\cdots\times e^{-\frac{k-1}n}=e^{-\frac{k(k-1)}{2n}}\le 1-p_0。

放到题目里，有 n=10^5，令 k=10^3，计算得 e^{-\frac{k(k-1)}{2n}}\approx 0.007，即有 p_0=99.3\% 的概率在随机求 10^3 个 f(x) 后找到相同值。故复杂度大约为 O(nk)\approx10^8。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
using ll = long long;
ll seed, n, a[maxn];
ll nextRand()
{
    static ll x = seed;
    x ^= x << 11;
    x ^= x >> 45;
    x ^= x << 14;
    return (x % n + n) % n;
}
signed main()
{
    cin.tie(0)->ios::sync_with_stdio(false);
    cin >> n >> seed;
    for (int i = 0; i < n; ++i)
    {
        a[i] = nextRand();
    }
    map<ll, ll> m;
    for (int x = 0; x < n; ++x)
    {
        ll cnt = 0;
        for (ll i = 0; i < n; ++i)
        {
            cnt = (cnt + (a[i] ^ (i * x))) % n;
        }
        if (m.find(cnt) != m.end())
        {
            cout << m[cnt] << ' ' << x;
            return 0;
        }
        m[cnt] = x;
    }
    return 0;
}