Editorial for divisible: Số đẹp 3

Hiểu bài toán

Bài toán yêu cầu đếm số lượng số nguyên không âm x trong khoảng từ L đến R (bao gồm L và R) sao cho x chia hết cho ít nhất một trong ba số 4, 7, hoặc 11. Đây là bài toán đếm số lượng số chia hết cho một trong các ước số trong một khoảng.

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

Cách Brute Force

#include <iostream>
using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        long long L, R;
        cin >> L >> R;
        long long count = 0;
        for (long long x = L; x <= R; x++) {
            if (x % 4 == 0 || x % 7 == 0 || x % 11 == 0) {
                count++;
            }
        }
        cout << count << endl;
    }
    return 0;
}

• Time Complexity: O((R-L+1)) per test case, too slow for R up to 10^12
• Space Complexity: O(1)

Duyệt qua từng số x từ L đến R, kiểm tra xem x có chia hết cho 4, 7, hay 11 không. Cách này chỉ hiệu quả với R-L nhỏ (Subtask 1), không khả thi với R lên tới 10^12.

Cách Inclusion-Exclusion Principle

#include <stdio.h>

long long count_multiples(long long L, long long R, long long divisor) {
    if (L > R) return 0;
    long long start = (L % divisor == 0) ? L : L + (divisor - L % divisor);
    long long end = (R % divisor == 0) ? R : R - (R % divisor);
    if (start > R || end < L) return 0;
    return (end - start) / divisor + 1;
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        long long L, R;
        scanf("%lld %lld", &L, &R);
        long long count4 = count_multiples(L, R, 4);
        long long count7 = count_multiples(L, R, 7);
        long long count11 = count_multiples(L, R, 11);
        long long count4_7 = count_multiples(L, R, 28); // lcm(4,7)
        long long count4_11 = count_multiples(L, R, 44); // lcm(4,11)
        long long count7_11 = count_multiples(L, R, 77); // lcm(7,11)
        long long count4_7_11 = count_multiples(L, R, 308); // lcm(4,7,11)
        long long result = count4 + count7 + count11 - count4_7 - count4_11 - count7_11 + count4_7_11;
        printf("%lld\n", result);
    }
    return 0;
}

• Time Complexity: O(1) per test case
• Space Complexity: O(1)

Sử dụng quy tắc bù trừ (Inclusion-Exclusion Principle). Đếm số lượng số chia hết cho từng số (4, 7, 11), sau đó trừ đi các số chia hết cho bội chung của từng cặp (28, 44, 77), và cộng lại các số chia hết cho bội chung của cả ba (308). Số lượng số chia hết cho k trong khoảng [L, R] tính bằng: floor(R/k) - floor((L-1)/k).

Cách Direct Formula (Optimized)

#include <stdio.h>

long long check(long long a, long long b, long long c) {
    long long res;
    if (a % c == 0)
        res = b / c - a / c + 1;
    else
        res = b / c - a / c;
    return res;
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        long long l, r;
        scanf("%lld %lld", &l, &r);
        long long res;
        res = check(l, r, 4) + check(l, r, 7) + check(l, r, 11);
        res -= check(l, r, 28) + check(l, r, 44) + check(l, r, 77) - check(l, r, 308);
        printf("%lld\n", res);
    }
    return 0;
}

• Time Complexity: O(1) per test case
• Space Complexity: O(1)

Đây là cách tính trực tiếp tương tự như Inclusion-Exclusion nhưng được viết gọn. Hàm check(a, b, c) đếm số số trong [a, b] chia hết cho c. Nếu a chia hết cho c, số đầu tiên được tính là a, ngược lại là số tiếp theo. Công thức Inclusion-Exclusion được áp dụng y hệt.

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

Bài học kinh nghiệm

• Bài toán đếm số chia hết trong khoảng [L, R] có thể giải quyết bằng công thức: floor(R/k) - floor((L-1)/k) hoặc các biến thể tương tự.
• Để đếm số lượng số chia hết cho ít nhất một trong các số, ta cần sử dụng Principle of Inclusion-Exclusion (PIE) để tránh đếm trùng các số chia hết cho nhiều ước số.
• Với các ước số 4, 7, 11, ta cần tính bội chung của chúng: lcm(4,7)=28, lcm(4,11)=44, lcm(7,11)=77, lcm(4,7,11)=308.

Lỗi thường gặp

• Overflow số nguyên khi tính toán với R lên tới 10^12. Cần sử dụng kiểu dữ liệu 64-bit (long long trong C/C++).
• Sai công thức đếm số chia hết trong khoảng [L, R], đặc biệt khi L chia hết cho divisor.
• Quên xử lý trường hợp L > R (mặc dù đề bài đảm bảo L <= R).