整数运算中a > c//b是否为a*b > c的无溢出安全等价形式？

一、a * b > c 与 a > c // b 的推导正确性 #

首先明确前提：所有变量均为正整数（若包含负数，向下取整逻辑会发生变化，推导不再成立）。

你的推导是正确的，验证如下：

1. 正向推导：若 a * b > c，两边除以正整数 b 得 a > c / b。根据向下取整定义，c // b = floor(c / b)，必然满足 floor(c / b) <= c / b，因此 a > c / b >= c // b，可得 a > c // b。
2. 反向推导：通过逆否命题验证——原命题「若 a * b <= c，则 a <= c // b」成立：
   当 a * b <= c 时，a <= c / b；结合向下取整定义 floor(c / b) <= c / b < floor(c / b) + 1，且 a 是整数，因此 a <= floor(c / b)，即 a <= c // b。
   逆否命题「若 a > c // b，则 a * b > c」自然成立。

因此在正整数前提下，忽略溢出的数学层面上，a * b > c 与 a > c // b 完全等价，后者可用于C++代码中避免乘法溢出。

二、a * b >= c 的等价判断与安全实现 #

你关于「a * b >= c 与 a >= c // b 不等价」的结论是正确的：正向推导成立（若 a * b >= c，则 a >= c / b >= c // b，故 a >= c // b），但反向推导不成立——比如你举的例子：a=2、b=2、c=5，2 >= 5//2（即 2>=2）成立，但 2*2=4 >=5 不成立。

安全判断 a * b >= c 的方法（无溢出） #

针对正整数场景，可通过以下方式实现：

方法1：结合整除与取余判断

利用「当 a == c//b 时，仅当 c 能被 b 整除，a*b 才等于 c」的逻辑，组合判断：

// C++代码示例，假设a、b、c均为正整数
bool is_ab_ge_c(int a, int b, int c) {
    return (a > c / b) || (a == c / b && c % b == 0);
}

注：C++中整数除法/对正整数是向下取整，等价于Python的//。

方法2：利用减法转换除法

a * b >= c 等价于 a > (c - 1) / b（适用于 c > 0 的场景），推导如下：

• 若 c 能被 b 整除，c = k*b，则 (c-1)/b = (k*b-1)/b 向下取整为 k-1，a > k-1 即 a >=k，此时 a*b >=k*b =c；
• 若 c 不能被 b 整除，c = k*b + r（0<r<b），则 (c-1)/b 向下取整为 k，a>k 即 a>=k+1，此时 a*b >=(k+1)*b >k*b +r =c。
  该方法只需一次除法，完全避免乘法溢出，C++代码示例：

bool is_ab_ge_c(int a, int b, int c) {
    if (c == 0) return true; // 若c为0，正整数乘积必然>=0
    return a > (c - 1) / b;
}

方法3：溢出预判（针对有符号整数）

若需处理可能超出类型最大值的场景，可先预判乘法是否会溢出：

#include <climits>

bool is_ab_ge_c(int a, int b, int c) {
    if (a <= 0 || b <= 0) {
        // 根据实际需求处理非正整数场景，此处假设仅支持正整数
        return false;
    }
    // 预判a*b是否会溢出：若a > INT_MAX/b，则a*b必然超过int最大值，远大于c（c为int）
    if (a > INT_MAX / b) {
        return true;
    }
    // 无溢出时直接比较乘积
    return (a * b) >= c;
}

内容的提问来源于stack exchange，提问作者qwr