带余除法

题意

输入被除数和非零除数，输出 C/C++ 默认整数除法的商和余数。

思路

先按向零规则求商 $q$ ，再用 $r=a-qb$ 计算余数。这样余数一定与被除数满足等式，也避免 Python % 对负数的符号规则和 C++ 不同。

代码

Python代码

python

1
2
3
4
5
6
7
8def trunc_dividend(dividend, divisor):
    quotient = abs(dividend) // abs(divisor)
    return quotient if dividend * divisor >= 0 else -quotient


dividend, divisor = map(int, input().split())
quotient = trunc_dividend(dividend, divisor)
print(quotient, dividend - quotient * divisor)

C++代码

cpp

1
2
3
4
5
6
7
8#include <cstdio>

int main(){
    int a,b,c;
    scanf("%d%d",&a,&b);
    printf("%d %d",a/b,a%b);
    return 0;
}

复杂度

时间复杂度和额外空间复杂度均为 $O(1)$ 。

总结

跨语言处理除法时，先定义商的舍入方向，再由等式恢复余数最稳妥。

目录

题意

思路

代码

Python代码

C++代码

复杂度

总结