数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究使用 C++ 查找 N! 在 B 进制表示下的尾随零个数
在这篇文章中，我们将了解如何找到给定数字 N 的阶乘在 B 进制表示下的尾随零个数的问题。例如
Input : N = 7 Base = 2 Output : 4 Explanation : fact(7) = 5040 in base10 and 1001110110000 in base16 having 4 trailing zero. Input : N = 11 Base = 5 Output : 2 Explanation : fact(11) = 39916800 in base10 and 40204314200 in base16 having 2 trailing zeroes.
让我们首先回顾一下将任何十进制数从一个进制转换为另一个进制的过程。让我们以将 (5040)10 转换为 (?)2 为例
即，将数字除以 2 并保留余数，直到数字无法再被除为止。结果将是余数的逆序。
因此，我们有 4 个尾随零，当 2 除以该数字时余数为 0，我们得到了这个尾随零。
5040 的素因子分解 = 24 * 56711 * 3381 * 181，这意味着 2 除以 5040，余数为 0，共 4 次，等于尾随零的个数。通过这种方式，我们可以计算尾随零的个数。
寻找解决方案的方法
我们上面讨论了查找尾随零个数的方法。我们需要找到 N! 中 B 的最高幂，假设基数 B = 14，那么 14 在 14 进制下表示为 10，即 (14)10 = (10)14。这也被称为勒让德公式。
上述方法的 C++ 代码
这是我们可以用作输入来解决给定问题的 C++ 语法：
示例
#include <bits/stdc++.h>
using namespace std;
vector < pair < int, int >> primeFactorsofBase(int Base) {
// declaring factors to store prime factors
// along with occurence in factorisation of 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 = Base / i;
count++;
}
factors.push_back (make_pair (i, count));
}
}
return factors;
}
int main () {
int N = 11, Base = 5;
// finding the largest power of Base that divides factorial N.
vector < pair < int, int >>prime_factors;
// finding prime factors by primeFactorsofBase() function.
prime_factors = primeFactorsofBase(Base);
int result = INT_MAX;
for (int i = 0; i < prime_factors.size (); i++) {
// calculating minimum power.
int count = 0;
int r = prime_factors[i].first;
while (r <= N){
count += (N / r);
r = r * prime_factors[i].first;
}
result = min (result, count / prime_factors[i].second);
}
//printing trailing zeroes stored in result.
cout << "Number of trailing zeroes: " <<result;
return 0;
}输出
Number of trailing zeroes: 2
上述代码的解释
- 使用向量查找基数的最大幂。
- 要计算最大幂，请使用向量计算素因子以存储所有素因子。
- 然后计算基数的所有素因子的最小幂。
- 最后，打印结果。
结论
在这篇文章中，我们解决了查找 N! 在 B 进制表示下的尾随零个数的问题，我们使用勒让德公式来解决这个问题。我们还编写了 C++ 代码来解决同样的问题。您可以使用其他语言（如 Java、C、Python 等）编写此代码。希望您觉得这篇文章有所帮助。
更新于：2021年11月25日
224 次浏览
广告