Hiểu bài toán

Cho hai số nguyên dương N và K. Đếm số lượng bộ ba số nguyên dương (a, b, c) sao cho $1 \le a, b, c \le N$ và $a+b$, $b+c$, $c+a$ đều là bội số của K. Điều này tương đương với:

1. $a+b \equiv 0 \pmod K$
2. $b+c \equiv 0 \pmod K$
3. $c+a \equiv 0 \pmod K$

Từ các phương trình này, ta có thể suy ra: $(a+b) + (b+c) - (c+a) = 2b \equiv 0 \pmod K \implies 2b \equiv 0 \pmod K$. Tương tự cho a và c. Do đó, a, b, c phải có dạng $x \pmod K$ sao cho $2x \equiv 0 \pmod K$.

Nếu $K$ là số lẻ, nghiệm duy nhất là $x \equiv 0 \pmod K$. Khi đó a, b, c phải là bội của K. Nếu $K$ là số chẵn, có hai trường hợp:

• $x \equiv 0 \pmod K$ (a, b, c là bội của K).
• $x \equiv K/2 \pmod K$ (a, b, c có dư là K/2).

Bài toán quy về đếm số lượng số trong khoảng [1, N] thuộc các nhóm dư trên rồi tính tổ hợp.

Các cách tiếp cận

Cách Brute Force (Quy hoạch toàn bộ)

#include <iostream>
using namespace std;

int main() {
    long long n, k;
    cin >> n >> k;
    long long ans = 0;
    for (long long a = 1; a <= n; a++) {
        for (long long b = 1; b <= n; b++) {
            if ((a + b) % k != 0) continue;
            for (long long c = 1; c <= n; c++) {
                if ((b + c) % k == 0 && (c + a) % k == 0) {
                    ans++;
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

• Time Complexity: O(N^3)
• Space Complexity: O(1)

Duyệt qua tất cả các bộ ba (a, b, c) từ 1 đến N và kiểm tra điều kiện đề bài. Phương pháp này chỉ khả thi với N rất nhỏ (ví dụ N <= 20). Với N và K lên tới $2 \times 10^5$, phương pháp này chắc chắn bị TLE (Time Limit Exceeded).

Cách Quy hoạch theo số dư (Math Approach)

#include <iostream>
#include <cmath>

using namespace std;

int main() {
    long long n, k;
    cin >> n >> k;

    // Đếm số lượng số trong [1, N] có dư 0 khi chia cho K
    long long count0 = n / k;

    // Đếm số lượng số có dư K/2 (chỉ applicable nếu K chẵn)
    long long count_half = 0;
    if (k % 2 == 0) {
        // Số có dạng K/2 + m*K. Số nhỏ nhất là K/2 (nếu K/2 >= 1).
        // Công thức đếm: (N - K/2) / K + 1
        count_half = (n + k / 2) / k;
    }

    long long total = count0 * count0 * count0;
    if (k % 2 == 0) {
        total += count_half * count_half * count_half;
    }

    cout << total << endl;

    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Phân tích điều kiện $a+b \equiv 0 \pmod K \implies a \equiv -b \pmod K$. Kết hợp với $2b \equiv 0 \pmod K$, ta thấy a, b, c phải cùng chung một loại số dư thỏa mãn $2x \equiv 0 \pmod K$. Chỉ có 2 loại số dư khả dĩ: 0 (luôn thỏa mãn) và K/2 (chỉ khi K chẵn).

• Nếu K lẻ: Chỉ có thể chọn a, b, c đều có dư 0. Số lượng số trong [1, N] có dư 0 là $\lfloor N/K \rfloor$. Số bộ ba là $(\lfloor N/K \rfloor)^3$.
• Nếu K chẵn: Có thể chọn cả 3 số có dư 0, hoặc cả 3 số có dư K/2.
  • Số lượng số có dư 0: $N/K$.
  • Số lượng số có dư K/2: Số lượng số $x \le N$ sao cho $x \equiv K/2 \pmod K$. Dãy số này là $K/2, K/2 + K, K/2 + 2K, ...$. Số lượng là $\lfloor (N - K/2)/K \rfloor + 1$. Công thức gọn là $\lfloor (N + K/2)/K \rfloor$.
  • Tổng số bộ ba là tổng số lượng cách chọn của từng loại.

Cách Suy luận Logic (Optimal)

// Same as Approach 2

• Time Complexity: O(1)
• Space Complexity: O(1)

Đây là cách tiếp cận tối ưu nhất, dựa trên suy luận logic chặt chẽ để loại bỏ các khả năng không cần thiết.

1. Từ $a+b \equiv 0 \pmod K$ và $b+c \equiv 0 \pmod K$, ta có $a \equiv c \pmod K$.
2. Tương tự, ta suy luận ra $a \equiv b \equiv c \pmod K$.
3. Thay vào $a+b \equiv 0 \pmod K$, ta có $2a \equiv 0 \pmod K$.
4. Bài toán trở thành đếm số lượng $x \in {0, K/2}$ (nếu K chẵn) hoặc $x=0$ (nếu K lẻ) thỏa mãn $2x \equiv 0 \pmod K$, và sau đó tính số cách chọn $a, b, c$ có cùng số dư $x$.

Cách tính số lượng số trong [1, N] có số dư $r$ modulo $K$:

• Nếu $r = 0$: Số lượng là $N / K$.
• Nếu $r > 0$: Số lượng là $\lfloor (N - r) / K \rfloor + 1$.

Logic này đưa đến thuật toán $O(1)$ như ở Approach 2.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Phép cộng module kết hợp với trừ để tìm quan hệ giữa các biến (ví dụ: $(a+b) - (a+c) = b-c$).
• Nếu $a \equiv b \pmod K$ và $a+b \equiv 0 \pmod K$ thì $2a \equiv 0 \pmod K$. Điều này giới hạn các giá trị số dư có thể của a, b, c xuống rất ít (chỉ 1 hoặc 2 giá trị).
• Bài toán đếm bộ ba có thể tách thành các trường hợp độc lập (cùng dư 0, cùng dư K/2) và tính tổng.

Lỗi thường gặp

• Sai công thức đếm số lượng số có số dư K/2: Cần chú ý số đầu tiên là K/2 (nếu K/2 >= 1), không phải 0. Ví dụ: N=3, K=2, số dư 2/2=1. Các số là 1, 3. Số lượng là 2. Công thức (N+K/2)/K = (3+1)/2 = 2 là đúng. Nếu dùng N/K thì sai.
• Kiểu dữ liệu: N và K lên tới $2 \times 10^5$, nhưng kết quả có thể lên tới $(200000)^3$ (khoảng $8 \times 10^{15}$), cần dùng long long (64-bit) để tránh tràn số.