นับคู่มี序 (i,j) ที่ผลรวมหาร A และ B ลงตัวใน C++

ภาพรวมปัญหา

ให้ N, M, A, B ต้องการนับคู่มี序 (i, j) ที่ 1≤i≤N, 1≤j≤M และ (i+j) หาร A ลงตัว และหาร B ลงตัว

ตัวอย่าง

Input: N=5, M=10, A=2, B=3

Output: 9

คำอธิบาย: (1,5), (2,4), (2,10), (3,3), (3,9), (4,2), (4,8), (5,1), (5,7)

Input: N=10, M=10, A=10, B=11

Output: 0

ข้อสังเกตสำคัญ

(i+j) หาร A และ B ลงตัว ⟺ (i+j) หาร LCM(A,B) ลงตัว

ให้ L = LCM(A, B) = A × B / GCD(A, B)

แนวทางแก้ปัญหา (Naive)

1. วนลูป i=1..N, j=1..M
2. ถ้า (i+j)%A==0 && (i+j)%B==0 ให้เพิ่ม count

โค้ดตัวอย่าง (Naive)

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

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

int main() {
    int N = 50, M = 100, A = 5, B = 10;
    cout << "Ordered pairs: " << sumDivisible(N, M, A, B);
    return 0;
}

ผลลัพธ์

Ordered pairs (i,j) where (i+j) is divisible by both A & B: 500

แนวทางคณิตศาสตร์ O(1) หรือ O(N)

สำหรับแต่ละ i (1..N) ต้องการ j ที่ (i+j) ≡ 0 (mod L) → j ≡ -i (mod L)

จำนวน j ใน [1, M] ที่ ≡ r (mod L) คือ: ⌊(M - r) / L⌋ + 1 (ถ้า r ≥ 1 และ r ≤ M)

โค้ดที่ปรับปรุงแล้ว O(N)

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

int sumDivisible_fast(int n, int m, int a, int b) {
    long long L = 1LL * a / gcd(a, b) * b; // LCM
    long long count = 0;
    
    for (int i = 1; i <= n; i++) {
        int r = ((-i) % L + L) % L; // j ≡ -i (mod L), r ใน [0, L-1]
        if (r == 0) r = L; // j ต้อง ≥ 1
        if (r > m) continue;
        count += (m - r) / L + 1;
    }
    return count;
}

ความซับซ้อน

สูตร O(1) แบบเต็ม

จำนวนคู่ = Σ_{k=1}^{⌊(N+M)/L⌋} (จำนวน (i,j) ที่ i+j = kL)

สามารถคำนวณได้โดยตรงจากเรขาคณิตของเส้น i+j = constant ในกรอบ N×M