Tổng N số tự nhiên đầu tiên chia hết cho X hoặc Y

Tổng các số tự nhiên ≤ n chia hết cho X hoặc Y. Hai phương pháp:

Phương pháp 1: Vòng lặp

#include <stdio.h>
int main(void) {
    int n = 54, x = 2, y = 5, sum = 0;
    for (int i = 0; i <= n; i++)
        if (i % x == 0 || i % y == 0)
            sum += i;
    printf("Tong %d so tu nhien chia het cho %d va %d la %d", n, x, y, sum);
    return 0;
}

Kết quả: 881

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

Sử dụng công thức cấp số cộng cho bội số:

S(n/x) = (n/x)/2 * (2x + (n/x - 1)x)
S(n/y) = (n/y)/2 * (2y + (n/y - 1)y)
S(n/(xy)) = (n/(xy))/2 * (2xy + (n/(xy) - 1)xy)
Tổng = S(n/x) + S(n/y) - S(n/(xy))

#include <stdio.h>
int main() {
    int n = 54, x = 2, y = 5;
    int Sx = ((n/x)) * (2*x + (n/x - 1)*x) / 2;
    int Sy = ((n/y)) * (2*y + (n/y - 1)*y) / 2;
    int Sxy = ((n/(x*y))) * (2*(x*y) + (n/(x*y) - 1)*(x*y)) / 2;
    int sum = Sx + Sy - Sxy;
    printf("Tong = %d", sum);
    return 0;
}

Kết quả: 881. Phương pháp 2 tốt hơn cho n lớn (O(1) vs O(n)).