使用整数除法时，将“a/(b*c)”替换为“a/b/c”是否安全？

更换是否安全a/(b*c) with a/b/c对正整数使用整数除法时a,b,c，或者我有丢失信息的风险吗？

我做了一些随机测试，但找不到例子a/(b*c) != a/b/c，所以我很确定它是安全的，但不太确定如何证明它。

谢谢。

数学

作为数学表达式，⌊a/(bc)⌋ and ⌊⌊a/b⌋/c⌋每当b是非零并且c是一个正整数（特别是对于正整数a, b, c）。这类事情的标准参考书是一本令人愉快的书具体数学：计算机科学的基础作者：格雷厄姆、高德纳和帕塔什尼克。其中，第 3 章主要讨论地板和天花板，第 71 页证明了这一点，作为更一般结果的一部分：

在上面的3.10中，你可以定义x = a/b（数学，即实数除法），以及f(x) = x/c（再次精确除法），并将它们插入左侧的结果中⌊f(x)⌋ = ⌊f(⌊x⌋)⌋（核实条件后f按住此处）以获得⌊a/(bc)⌋在 LHS 上等于⌊⌊a/b⌋/c⌋在右侧。

如果我们不想依赖书中的参考文献，我们可以证明⌊a/(bc)⌋ = ⌊⌊a/b⌋/c⌋直接用他们的方法。请注意，与x = a/b（真实数字），我们想要证明的是⌊x/c⌋ = ⌊⌊x⌋/c⌋. So:

• if x是一个整数，那么没有什么可以证明的，因为x = ⌊x⌋.
• 否则，⌊x⌋ < x, so ⌊x⌋/c < x/c意思就是⌊⌊x⌋/c⌋ ≤ ⌊x/c⌋。 （我们想证明它是相等的。）为了矛盾起见，假设⌊⌊x⌋/c⌋ < ⌊x/c⌋那么一定有一个数 y 使得⌊x⌋ < y ≤ x and y/c = ⌊x/c⌋。 （当我们增加一个数字⌊x⌋ to x并考虑除以c，在某个地方我们必须达到精确值⌊x/c⌋.)但这意味着y = c*⌊x/c⌋是一个介于⌊x⌋ and x，这是一个矛盾！

这就证明了结果。

编程

#include <stdio.h>

int main() {
  unsigned int a = 142857;
  unsigned int b = 65537;
  unsigned int c = 65537;

  printf("a/(b*c) = %d\n", a/(b*c));
  printf("a/b/c = %d\n", a/b/c);
}

打印（使用 32 位整数），

a/(b*c) = 1
a/b/c = 0

（我使用无符号整数作为它们的溢出行为是明确的 https://stackoverflow.com/questions/18195715/why-is-unsigned-integer-overflow-defined-behavior-but-signed-integer-overflow-is，所以上面的输出是有保证的。对于有符号整数，溢出是未定义的行为，因此程序实际上可以打印（或执行）anything，这只会强化结果可能不同的观点。）

但如果你没有溢出，那么你在程序中得到的值就等于它们的数学值（即，a/(b*c)在你的代码中等于数学值⌊a/(bc)⌋, and a/b/c代码中等于数学值⌊⌊a/b⌋/c⌋），我们已经证明它们是相等的。所以更换是安全的a/(b*c)在代码中a/b/c when b*c足够小，不会溢出。