Hướng dẫn cho Không chia hết

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: SPyofgame

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

C++
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

C++
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

C++
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;
}

Bình luận