Hiểu bài toán

Cho ba số nguyên dương d, a, b. Gọi P là tích của các số nguyên x nằm trong khoảng [a, b] và chia hết cho d. Yêu cầu tìm số lượng số 0 tận cùng của P (tức số mũ của thừa số 2 và 5 trong phân tích thừa số của P, lấy min của hai số mũ đó).

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

Cách Brute Force

#include <iostream>
using namespace std;
int count_factor(long long n, int p) {
    int count = 0;
    while (n % p == 0) {
        count++;
        n /= p;
    }
    return count;
}
long long d, a, b;
int main() {
    cin >> d >> a >> b;
    long long start = (a + d - 1) / d;
    long long end = b / d;
    long long twos = 0, fives = 0;
    for (long long k = start; k <= end; ++k) {
        long long x = k * d;
        twos += count_factor(x, 2);
        fives += count_factor(x, 5);
    }
    cout << min(twos, fives) << endl;
    return 0;
}

• Time Complexity: O((b/d) * log(max(b, d)))
• Space Complexity: O(1)

Duyệt qua tất cả các số k từ start đến end (start = ceil(a/d), end = floor(b/d)), mỗi k tương ứng với x = k*d. Với mỗi x, đếm số mũ của 2 và 5 trong x, cộng dồn vào biến twos và fives. Cuối cùng, in ra min(twos, fives).

Cách Optimized Counting

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

ll fact_exp(ll n, int p) {
    ll res = 0;
    while (n) {
        res += n / p;
        n /= p;
    }
    return res;
}

int count_p(ll n, int p) {
    int cnt = 0;
    while (n % p == 0) {
        n /= p;
        cnt++;
    }
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll d, a, b;
    cin >> d >> a >> b;

    ll L = (a + d - 1) / d;
    ll R = b / d;
    if (L > R) {
        cout << 0;
        return 0;
    }

    ll len = R - L + 1;
    int v2d = count_p(d, 2);
    int v5d = count_p(d, 5);

    ll cnt2 = len * v2d + fact_exp(R, 2) - fact_exp(L - 1, 2);
    ll cnt5 = len * v5d + fact_exp(R, 5) - fact_exp(L - 1, 5);

    cout << min(cnt2, cnt5) << "\n";
}

• Time Complexity: O(log b)
• Space Complexity: O(1)

P = d^N * (L * (L+1) * ... * R) trong đó N = R - L + 1 là số lượng số. Số mũ của 2 trong P là N * (số mũ của 2 trong d) + (số mũ của 2 trong (R! / (L-1)!)). Tương tự cho 5. Sử dụng hàm tính số mũ của p trong n! để tính toán trong thời gian logarit.

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

Bài học kinh nghiệm

• Bài toán có thể biến đổi thành bài toán tìm số mũ của 2 và 5 trong tích các số từ L đến R (L, R là các chỉ số sau khi chuẩn hóa về d).
• Số mũ của p trong tích các số từ L đến R bằng số mũ của p trong R! trừ đi số mũ của p trong (L-1)!. Đây là kỹ thuật chuẩn để đếm số mũ của một số nguyên tố trong một tích阶乘.

Lỗi thường gặp

• Làm tròn sai khi tính số lượng số chia hết cho d trong khoảng [a, b] (cần dùng ceil cho a và floor cho b).
• Quên nhân số mũ của 2 và 5 từ d vào kết quả cuối cùng.