Đếm số 0 đuôi trong tích (1^1)*(2^2)*(3^3)*(4^4)*... trong C++

Cho một số nguyên num làm đầu vào. Mục tiêu là tìm số lượng số 0 đuôi trong tích 1^1 × 2^2 × 3^3 × ... × num^num.

Ví dụ

Đầu vào

num=5

Đầu ra

Số 0 đuôi trong tích (1^1)*(2^2)*(3^3)*(4^4)*.. là: 5

Giải thích

Số lượng 2 và 5 trong tích sẽ là: 1^1 * 2^2 * 3^3 * 4^4 * 5^5 = 1^1 * 2^2 * 3^3 * (2^2)^4 * 5^5. Vậy tổng cộng 10 số 2 và 5 số 5, min là 5 nên số 0 đuôi sẽ là 5.

Đầu vào

num=10

Đầu ra

Số 0 đuôi trong tích (1^1)*(2^2)*(3^3)*(4^4)*.. là: 15

Giải thích

Số lượng 2 và 5 trong tích: 1^1 * 2^2 * 3^3 * 4^4 * 5^5 * 6^6 * 7^7 * 8^8 * 9^9 * 10^10 = 1^1 * 2^2 * 3^3 * 4^4 * 5^5 * 6^6 * 7^7 * 8^8 * 9^9 * (2*5)^10. Vậy tổng 20 số 2 và 15 số 5, min là 15 nên số 0 đuôi là 15.

Phương pháp sử dụng

Trong phương pháp này, chúng ta sẽ đếm số lượng 2 và 5 trong phân tích thừa số nguyên tố của mỗi số trong tích. Vì mỗi số được lũy thừa theo chính nó, nên min của số lượng 2 hoặc 5 trong phân tích sẽ cho số 0 đuôi. Vì mỗi cặp 2*5 thêm một số 0 vào tích.

• Nhận số nguyên num làm đầu vào.
• Hàm count_trailing(int num) nhận num và trả về số 0 đuôi trong tích.
• Khởi tạo biến đếm ban đầu là 0.
• Tạo biến temp_2 = 0, temp_5 = 0 cho số lượng 2 và 5.
• Duyệt bằng vòng lặp for từ i=1 đến i<=num.
• Lấy temp là i.
• Khi temp chia hết cho 2 thì giảm nó thành một nửa và cộng i vào biến đếm temp_2 là số lượng 2.
• Khi temp chia hết cho 5 thì chia nó cho 5 và cộng i vào biến đếm temp_5 là số lượng 5.
• Lấy biến đếm là min của hai biến đếm bằng count = min(temp_2, temp_5).
• Trả về biến đếm làm kết quả.

Ví dụ mã

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

int count_trailing(int num) {
    int count = 0;
    int temp_2 = 0;
    int temp_5 = 0;
    
    for (int i = 1; i <= num; i++) {
        int temp = i;
        
        while (temp % 2 == 0 && temp > 0) {
            temp = temp / 2;
            temp_2 = temp_2 + i;
        }
        
        while (temp % 5 == 0 && temp > 0) {
            temp = temp / 5;
            temp_5 = temp_5 + i;
        }
    }
    
    count = min(temp_2, temp_5);
    return count;
}

int main() {
    int num = 5;
    cout << "Số 0 đuôi trong tích (1^1)*(2^2)*(3^3)*(4^4)*.. là: " << count_trailing(num);
    return 0;
}

Đầu ra

Nếu chạy mã trên, sẽ tạo ra đầu ra sau:

Số 0 đuôi trong tích (1^1)*(2^2)*(3^3)*(4^4)*.. là: 5