使用 C++ 查找 N! 在 16 进制表示中的尾随零个数

在本文中，我们将了解如何解决查找给定数字 N 的阶乘在 16 进制表示中尾随零个数的问题，例如：

Input : N = 7
Output : 1
Explanation : fact(7) = 5040 in base10 and 13B0 in base16 having 1 trailing zero.

Input : N = 11
Output : 2
Explanation : fact(11) = 39916800 in base10 and 2611500 in base16 having 2 trailing zeroes.

让我们首先回顾一下将任何十进制数从一个进制转换为另一个进制的过程；让我们以将 (5040)10 转换为 (?)16 为例

即，将数字除以 16 并保留余数，直到数字无法再被除为止。结果将是余数的反序。

因此，我们得到一个尾随零，当 16 除以该数字时余数为 0，我们就得到了这个尾随零。

5040 的质因数分解 = 16¹ * 4⁵¹* 7¹, 这意味着 16 除以 5040 余数为 0，等于尾随零的个数。通过这种方式，我们可以计算尾随零的个数。

解决方法

我们上面讨论了查找尾随零个数的方法。我们也知道 16 = 2⁴，这意味着 N 除以四得到的最高次幂 2 将等于 16 的最高次幂。这也被称为勒让德公式。

上述方法的 C++ 代码

这是一个我们可以用作输入来解决给定问题的 C++ 语法：

示例

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

int main () {
   int n = 11;
   long long int count = 0;
   long long int value, power = 2;
   long long int result;

   do{
      value = n / power;
      count += value;
      power *= 2;
   }
   while (value != 0);

   // Count has the highest power of 2
   result = count / 4;
   cout << "Number of trailing zeroes in base 16 representation of N : " << result;
}

输出

Number of trailing zeroes in base 16 representation of N: 2

上述代码的解释

  • 我们用 2 初始化 power，因为我们需要计算 2 的最高次幂。
  • 在一个 while 循环中实现勒让德公式，我们用初始值为 2 的 power 除以 n，并用该值递增 count，用 2 递增 power。
  • 用 4 除以存储在 count 变量中的 2 的最高次幂之后。
  • 最后，我们打印结果。

结论

在本文中，我们解决了查找 N 的阶乘在 16 进制表示中尾随零个数的问题，我们使用勒让德公式解决了这个问题。我们还编写了 C++ 代码来解决同一个问题。您可以使用其他语言（如 Java、C、Python 等）编写此代码。我们希望您觉得这篇文章有所帮助。

更新于：2021-11-25

浏览量：144

开启您的 职业生涯

通过完成课程获得认证

开始学习
广告