这段代码如何从任何基数阶乘法中找到尾随零的数量？

下面的代码完美无缺，但我希望有人向我解释它背后的数学。 基本上，它是如何工作的？

#include  #include  /* atoi */ #define min(x, y) (((x) < (y)) ? (x) : (y)) int main(int argc, char* argv[]) { const int base = 16; int n,i,j,p,c,noz,k; n = 7; /* 7! = decimal 5040 or 0x13B0 - 1 trailing zero */ noz = n; j = base; /* Why do we start from 2 */ for (i=2; i  0) { c += k/i; k /= i; } noz = min(noz, c/p); } } printf("%d! has %d trailing zeros\n", n, noz); return 0; } 

Answer 1

请注意，问题相当于找到划分n的最高基数 ！ 。

如果基数是素数（让我们称之为p ），我们可以使用数论中的一个定理来计算除以n的p的最高幂！ ：

让我们将执行此操作的代码部分提取到函数中：

 int maximum_power_of_p_in_fac(int p, int n) { int mu = 0; while (n/p > 0) { mu += n/p; n /= p; } return mu; } 

现在如果基地是主要力量会发生什么？ 假设我们有base = p ^q 。 那么如果μ是p的最高幂，它除了n！ 和r = floor（μ/ q） ，我们有

（p ^ q）^ r = p ^（qr）除p ^μ除n！

和

（p ^ q）^（r + 1）= p ^（q（r + 1））> = p ^（μ+ 1）不分n！

所以r是n！中p ^ q的最大功率。 我们也为此编写一个函数：

 int maximum_power_of_pq_in_fac(int p, int q, int n) { return maximum_power_of_p_in_fac(p, n) / q; } 

那么如果基数是一般数呢？ 比方说吧

base = p ₁ ^{q ₁} p ₂ ^{q ₂} … p _m ^{q _m}

（这是基础的唯一主要因子分解）。 然后我们只解决所有p _i ^{q _i}的问题，并采取最小的：

 int maximum_power_of_base_in_fac(int base, int n) { int res = infinity; for every factor p^q in the prime factorization in base: res = min(res, maximum_power_of_pq_in_fac(p,q,n)); return res; } 

如何分解基数 ？ 好吧，我们可以使用试验分区，就像您的示例代码一样。 我们首先检查2是否是一个主要因素。 如果是，我们计算maximum_power_of_pq_in_fac并将base除以2，直到它不再被2整除。然后我们继续下一个候选因子：

 void factorize(int base) { for (int p = 2; p <= base; ++p) { if (base % p == 0) { // if base is divisible by p, p is a prime factor int q = 0; while (base % p == 0) { // compute q and get rid of all the p factors q++; base /= p; } // do something with factor p^q } // proceed with next candidate divisor } } 

通过仔细检查代码，您会发现它包含所有上述元素，只能放在一个循环中，这有点令人困惑。

更新：如果您感兴趣，您提出的算法具有复杂度O（base * log n） 。 您可以通过稍微调整素数因子分解例程轻松地使其为O（sqrt（base）* log n） ：

 void factorize(int base) { for (int p = 2; p*p <= base; ++p) { // only check prime factors up to sqrt(base) // ... same as before } if (base) { // there is exactly one prime factor > sqrt(base). // It certainly has multiplicity 1. // process prime factor base^1 } } 

当然，如果你想加快速度，你可以使用任何其他更复杂的素数因子分解算法。

Answer 2

基本上，它找到了base素数因子，其中i是素数，i ^p是基数因子，然后计算出n！中存在多少i因子，将其除以p，并跟踪结果的最小数量所有base因素。

所以回答代码中的问题：

1. 为什么我们从2开始
   • 因为2是最小的素数
2. 什么是p？
   • p是基数的素因子i的“幂”（所以i ^p是基数因子）
3. 这个循环背后的数学是什么？
   • 循环计数（ c ） n!中因子的数量n!