为什么以下两个因子尾随零的解决方案不相同？

我正在OJ网站上研究Factorial Trailing Zeroes问题.我搜索了问题并提出了一些解决方案:

int solution1(int n) {
  int result = 0;
  while (n > 0) {
    result += n /= 5;
  }
  return result;
}

int solution2(int n) {
  int result = 0;
  for (int i = 5;n >= i; i *= 5) {
    result += n/i;
  }
  return result;
}

尽管实施细节,我认为基本原理是相同的,可以在这里找到.因此我假设这两种解决方案是等价的.但是当我提交它们时,事实证明,当n = 1808548329时,解决方案2通过了502个测试用例中的500个并产生了错误的答案(结果= 452137080),而解决方案1得到了正确答案(结果= 452137076).

现在我很困惑这里出了问题.谁能告诉我为什么上述两种解决方案不相同？为什么solution1是正确的,solution2是错误的？

1> rici..：

---

因为i *= 5可以溢出.当它溢出时,你就不再有正确的比较了n.

说n = 1808548329.这是发生的事情:

             i              n      correct i
   -----------     ----------   ------------
             5     1808548329              5
            25     1808548329             25
           125     1808548329            125
           625     1808548329            625
          3125     1808548329           3125
         15625     1808548329          15625
         78125     1808548329          78125
        390625     1808548329         390625
       1953125     1808548329        1953125
       9765625     1808548329        9765625
      48828125     1808548329       48828125
     244140625     1808548329      244140625
    1220703125     1808548329     1220703125
    1808548329     1808548329     6103515625 # i overflows here; loop should stop
     452807053     1808548329    30517578125
   -2030932031     1808548329   152587890625
   -1564725563     1808548329   762939453125
     766306777     1808548329  3814697265625
    -463433411     1808548329 19073486328125
    1977800241     1808548329 95367431640625

我生成了以上内容:

#include 
int main() {
  int n = 1808548329;
  int i = 1;
  long long l = 1;
  do {
    i *= 5;
    l *= 5;
    printf("%14d %14d %14lld\n", i, n, l);
  } while (n >= i);
  return 0;
}

(在原始代码中,一些n/i值将是负数,只是为了使情况更加混乱.我没有包含一个n/i列;这样做可能很有趣.)

---

@AllenWang:溢出的五次幂恰好是测试用例的事实表明,无论是谁设计测试都准确地记住了这个错误.可以从这个问题中学到一些东西,其中没有一个与原始问题有很大关系.其中之一就是你在Google搜索中找到的很多代码实际上都有微妙的错误,所以不应该依赖它.另一个问题是,除了简单的逐个增量之外的任何东西的for循环都是可疑的; 如果限制为INTMAX,甚至一个一个的增量也会溢出.