在 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 次浏览

开启你的职业生涯

完成课程获得认证

开始学习