在 C++ 中計算 (1^1)*(2^2)*(3^3)*(4^4)*.. 的尾隨零個數

給定一個整數 num 作為輸入。目標是找到乘積 1¹ * 2² * 3³ * … * num^num 中尾隨零的個數。

例如

輸入

num=5

輸出

Count of number of trailing zeros in (1^1)*(2^2)*(3^3)*(4^4)*.. are: 5

解釋

The number of 2s and 5s in the product will be:
11 * 22* 33* 44* 55=11 * 22* 33* (22)4* 55. So total 10 2s and 5 5s, minimum is 5 so trailing zeroes will be 5.

輸入

num=10

輸出

Count of number of trailing zeros in (1^1)*(2^2)*(3^3)*(4^4)*.. are: 5

解釋

The number of 2s and 5s in the product will be:
11 *22*33*44*55*66 *77*88*99*1010 = 11 *22*33*44*55*66 *77*88*99*(2*5)10. So total 20 2s and 15 5s, minimum is 15 so trailing zeroes will be 15.

以下程式中使用的演算法如下 −

在這個方法中，我們將計算乘積中每個數字的素因數分解中 2 和 5 的個數。由於每個數字都自乘其自身冪次，因此 2 和 5 的個數的最小值將給出尾隨零的個數。因為每個 2*5 在乘積中都會增加一個 0。

• 將整數 num 作為輸入。

• 函式 count_trailing(int num) 獲取 num 並返回 (1^1)*(2^2)*(3^3)*(4^4)*..... 中尾隨零的個數。

• 將初始計數設定為 0。

• 使用變數 temp_2 = 0, temp_5 = 0 來分別計數 2 和 5 的個數。

• 使用 for 迴圈從 i=1 遍歷到 i<=num。

• 將 temp 設為 i。

• 當 temp 可被 2 整除時，將其減半，並將 i 加到 temp_2 中，作為 2 的個數。

• 當 temp 可被 5 整除時，將其除以 5，並將 i 加到 temp_5 中，作為 5 的個數。

• 使用 count = min(temp_2, temp_5) 計算兩個計數的最小值。

• 返回 count 作為結果。

示例

 線上演示

#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<<"Count of number of trailing zeros in (1^1)*(2^2)*(3^3)*(4^4)*.. are: "<<count_trailing(num);
   return 0;
}

輸出

如果我們執行上述程式碼，它將生成以下輸出：

Count of number of trailing zeros in (1^1)*(2^2)*(3^3)*(4^4)*.. are: 5

Sunidhi Bansal

更新於：2021年1月5日

143 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習