Đếm cặp (1..a, 1..b) có tổng chia hết N trong C++

Cho a, b, n. Đếm số cặp (x,y) với 1 ≤ x ≤ a, 1 ≤ y ≤ b sao cho (x+y) % n == 0.

Ví dụ: a=2, b=3, n=2 → 3 (cặp (1,1), (1,3), (2,2)).

Giải thuật: Vòng lặp lồng O(a*b). Có thể tối ưu bằng toán học modulo.

Ví dụ

#include <iostream>
using namespace std;

int Pair_a_b(int a, int b, int n) {
    int count = 0;
    for (int i = 1; i <= a; i++)
        for (int j = 1; j <= b; j++)
            if ((i + j) % n == 0) count++;
    return count;
}

int main() {
    int a = 2, b = 20, n = 4;
    cout << "Count: " << Pair_a_b(a, b, n);
    return 0;
}

Đầu ra

Count of pairs from 1 to a and 1 to b whose sum is divisible by N are: 10