Tóm tắt đề bài Cho ba số nguyên dương \((n, a, b)\).

Yêu cầu: Đếm số lượng số nguyên \((x \in [1, n])\) thỏa mãn \((x \bmod a = x\bmod b)\).

Dữ liệu đảm bảo: \((1 \le n, a, b, \le 10^{18})\).

Subtasks: \((75\%)\) số điểm: \((1 \le n, a, b \le 10^6)\). \((25\%)\) số điểm: Không có ràng buộc gì thêm.

Subtask 1

Duyệt qua từng số nguyên \((x \in [1, n])\), nếu (\(x\)) thỏa điều kiện, ta tăng đáp án lên (\(1\)).

Độ phức tạp thời gian: \((O \left( n \right))\).

#include <bits/stdc++.h>
using namespace std

long long n, a, b, res;

int main() {
    cin >> n >> a >> b;
    for (long long i = 1; i <= n; i++)
        if (i % a == i % b)
            res++;

    cout << res;

    return 0;
}

Subtask 2

Nhận xét

Giả sử ta có: \([ x \bmod a = x \bmod b = r \; (r \in \operatorname{N}) ]\) Khi đó: \([ (x - r) \bmod a = (x - r) \bmod b) = 0 ]\)

Nói cách khác, \((x - r)\) là bội của \((\operatorname{BCNN}(a, b))\) với \((r \in [0, \min(a, b) - 1])\).

Hay tương ứng với mỗi bội \((t)\) của \(\operatorname{BCNN}(a, b)\), ta có \(\min(a, b)\) đáp án, đó là: \( t, t + 1, \dots, t + \min(a, b) - 1 \)

Cảnh báo

Tuy nhiên, điều này không đúng với:

\(t = 0\), vì không tính đáp án \(0\). \(t + \min(a, b) - 1 \gt n\), vì có đáp án lớn hơn \(n\). Chúng ta cần xét riêng hai trường hợp bội \(t\) nhỏ nhất và lớn nhất trong khoảng \(n\)

Ta xét riêng ba trường hợp:

\(t = 0\) (bội nhỏ nhất), có \(\min(a, b) - 1\) đáp án. \(t + \min(a, b) - 1 \gt n\) (nếu có, \(t\) này là bội lớn nhất), có \(n - t + 1\) đáp án: \( t = \left \lfloor \frac {n} {\operatorname{BCNN}(a, b)} \right \rfloor \times \operatorname{BCNN}(a, b) \) \(t \gt 0\) và \(t + \min(a, b) - 1 \le n\), số lượng đáp án là số lượng bội \(t\) nhân cho số lượng \(r\) Số lượng bội \(t\) của \(\operatorname{BCNN}(a, b)\) thỏa \(t \gt 0\) và \(t + \min(a, b) - 1 \le n\): \( \left \lfloor \frac {n - \min(a, b) + 1} {\operatorname{BCNN}(a, b)} \right \rfloor \) Số lượng \(r\) (từ \(0\) đến \(\min(a, b) - 1\)): \( \min(a, b) \) Tính nhanh BCNN

Ta có: \( \operatorname{BCNN}(a, b) = \frac {a \times b} {\operatorname{UCLN}(a, b)} \) Có thể tính nhanh \(\operatorname{UCLN}(a, b)\) bằng câu lệnh __gcd() có sẵn của C++.

Lưu ý: Với giới hạn dữ liệu lớn, nếu cứ mặc kệ mà tính BCNN, giá trị có thể lên đến \(10^{36}\), dẫn đến tràn số.

Do đó ta cần xử lý khéo bằng cách dừng nếu nhận thấy số quá lớn!

Đáp án: \( (\min(a, b) - 1) + \left( n - \left \lfloor \frac {n} {\operatorname{BCNN}(a, b)} \right \rfloor \times \operatorname{BCNN}(a, b) + 1 \right) + \left \lfloor \frac {n - \min(a, b) + 1} {\operatorname{BCNN}(a, b)} \right \rfloor \times \left[ \min(a, b) \right] \)

Độ phức tạp thời gian: \(O \left( \log \min(a, b) \right)\)

Độ phức tạp của thuật toán Euclid để tìm BCNN.

#include <bits/stdc++.h>
using namespace std;

long long n, a, b;

long long __lcm(long long x, long long y) {
    long long z = x / __gcd(x, y);
    if (z > n / y) return n + 1;
    return (z * y);
}

int main() {
    cin >> n >> a >> b;
    long long t = __lcm(a, b);

    if (a > b) swap(a, b);

    long long res = min(n, (a - 1)) + ((max(0LL, n - a + 1) / t) * a);
    if ((n / t) * t > 0 && (n / t) * t + a - 1 > n)
        res += (n - (n / t) * t + 1);

    cout << res;

    return 0;
}