C++ Số chữ số 0 cuối trong biểu diễn cơ số B của N!

Tìm số chữ số 0 cuối (trailing zeros) của N! khi biểu diễn trong cơ số B. Ví dụ:

Input: N = 7, Base = 2 → Output: 4
Giải thích: 7! = 5040 (cơ số 10) = 1001110110000 (cơ số 2) có 4 số 0 cuối.

Input: N = 11, Base = 5 → Output: 2
Giải thích: 11! = 39916800 (cơ số 10) = 40204314200 (cơ số 5) có 2 số 0 cuối.

Số chữ số 0 cuối bằng số lần B chia hết N!. Đây là công thức Legendre mở rộng cho cơ số bất kỳ.

Phương pháp giải

Phân tích B thành thừa số nguyên tố: B = p₁^e₁ × p₂^e₂ × ... Với mỗi thừa số pᵢ, tính số mũ của pᵢ trong N! (theo Legendre: N/pᵢ + N/pᵢ² + ...). Kết quả là min(vᵢ / eᵢ) trên mọi i.

Ví dụ minh họa

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

vector<pair<int, int>> primeFactorsofBase(int Base) {
    vector<pair<int, int>> factors;
    for (int i = 2; Base != 1; i++) {
        if (Base % i == 0) {
            int count = 0;
            while (Base % i == 0) {
                Base /= i;
                count++;
            }
            factors.push_back({i, count});
        }
    }
    return factors;
}

int main() {
    int N = 11, Base = 5;
    auto prime_factors = primeFactorsofBase(Base);
    int result = INT_MAX;

    for (auto [p, e] : prime_factors) {
        int count = 0;
        long long power = p;
        while (power <= N) {
            count += N / power;
            power *= p;
        }
        result = min(result, count / e);
    }

    cout << "Số chữ số 0 cuối: " << result;
    return 0;
}

Kết quả

Số chữ số 0 cuối: 2

Giải thích

• Phân tích B thành thừa số nguyên tố.
• Với mỗi thừa số, tính số mũ trong N! bằng công thức Legendre.
• Lấy min của (số mũ / số lần xuất hiện trong B).

Kết luận

Đã giải bài toán trailing zeros trong cơ số B bằng công thức Legendre. Code C++ có thể chuyển sang Java, Python, C. Hy vọng hữu ích.