Tổng các bội số của hai số nhỏ hơn N trong C++

Cho M1, M2, N. Tính tổng các số < N là bội của M1 hoặc M2.

Ví dụ

Đầu vào: N = 13, M1 = 4, M2 = 6

Đầu ra: 20

Giải thích: Bội của 4,6 < 13: 4, 6, 8, 12. Tổng = 20

Phương pháp 1: Lặp đơn giản O(N)

int tongBoidon(int N, int M1, int M2) {
    int tong = 0;
    for (int i = 0; i < N; i++)
        if (i % M1 == 0 || i % M2 == 0) tong += i;
    return tong;
}

Phương pháp 2: Công thức toán học O(1)

Tổng bội của x đến n: Sum(x) = (n * (n+1) * x) / 2 với n = N/x

Áp dụng nguyên lý bao hàm - loại trừ:

Tổng = Tổng bội M1 + Tổng bội M2 - Tổng bội LCM(M1,M2)

Đơn giản hóa (giả sử M1, M2 nguyên tố cùng nhau): M1*M2

int tongBoidonNhanh(int N, int M1, int M2) {
    N--;
    long long n1 = N/M1, n2 = N/M2, n3 = N/(M1*M2);
    return (n1*(n1+1)*M1/2) + (n2*(n2+1)*M2/2) - (n3*(n3+1)*M1*M2/2);
}

Ví dụ mã nguồn

#include <iostream>
using namespace std;

int tongBoidonNhanh(int N, int M1, int M2) {
    N--;
    long long n1 = N/M1, n2 = N/M2, n3 = N/(M1*M2);
    return (n1*(n1+1)*M1/2) + (n2*(n2+1)*M2/2) - (n3*(n3+1)*M1*M2/2);
}

int main() {
    int N = 24, M1 = 4, M2 = 7;
    cout << "Tổng bội của " << M1 << " và " << M2 << " < " << N << " = " 
         << tongBoidonNhanh(N, M1, M2);
    return 0;
}

Kết quả

Tổng bội của 4 và 7 < 24 = 102