Spoiler Alert

Approach Brute-forces

Hint

• Trong k số liên tiếp có \(k - 1\) số không chia hết cho \(k\) cứ thế tuần hoàn ta tìm được đáp án

Reference AC code | \(O(?) \leq O(\frac{k}{n})\) query time | \(O(1)\) auxiliary space | Brute-forces

int query()
{
    int n = readInt();
    int k = readInt();

    int pre = 0;
    while (true)
    {
        int cur = max(0, k / n - pre);
        if (cur == 0) break;
        k += cur;
        pre += cur;
    }

    cout << k << endl;
    return 0;
}

Approach Binary-search

Hint

• Với mỗi số \(x\) chúng ta cần tìm \(f(x)\) là số lượng số bé hơn hoặc bằng \(x\) và không chia hết cho \(n\). Đáp án là số \(x\) nhỏ nhất thỏa mãn \(f(x) \geq k\)

Reference AC code | \(O(\log k)\) query time | \(O(1)\) auxiliary space | Binary-search

int query()
{
    int n = readInt();
    int k = readInt();

    int low = 0, high = 2 * k + 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (k <= 1LL * (n - 1) * mid)
            high = mid - 1;
        else 
             low = mid + 1;
    }

    ll block = 1LL * high * n;
    ll extra = k - 1LL * high * (n - 1);
    cout << block + extra << eol;
    return 0;
}

Approach Math

Hint

• \(\lfloor \frac{k - 1}{n - 1} \rfloor\) là số lượng các cụm \(n - 1\) phần tử (bỏ đi các bội \(n\))

• \(\lfloor \frac{k - 1}{n - 1} \rfloor \times n\) là vị trí đầu sau khi lấy đi các giá trị bội \(n\)

• \(k \mod (n - 1)\) là vị trí số cần tìm so với vị trí đầu (ta lấy trên đoạn [1..n - 1] nên khi \(k \equiv 1 \pmod{n - 1}\) ta tăng lên \(n - 1\))

• Kết quả là \(\lfloor \frac{k - 1}{n - 1} \rfloor \times n + k \mod (n - 1)\)

Reference AC code | \(O(1)\) query time | \(O(1)\) auxiliary space | Math

int query()
{
    int n = readInt();
    int k = readInt();

    int block = (k - 1) / (n - 1) * n;
    int extra = k % (n - 1);
    if (extra == 0) extra = n - 1;

    cout << block + extra << eol;
    return 0;
}