余数

理解

根据前面的整除的理解,我们类比一下得到 $a \% b = c$ : 一直用长度为 $b$ 的刀去砍 $a$ ,最后剩余的不中 $b$ 部分的长度为 $c$ ,显然 $0 \leqslant c < b$

`c++`中的取余

c++与python都有取余运算,但是有区别

有两个数 $a,b$ ,求 $a \% b$ 的值,如果 $a , b > 0$ ,那么c++与python的结果是一样的.但如果 $a \geqslant 0,b <0$ ,那么结果就不一样了

a = 10
b = -7
print(a % b)

int a = 10;
int b = -7;
cout << a % b << endl; // -3

为什么c++与python的结果不一样呢?怎么从数学的角度解释呢? TODO 后面有时间写

如果使c++得到与 python的结果一样呢?

int python_mod(int a,int b) {
    int c = b <0 ? -b:b;
    return (( a % b) +c) %c;
}

取余运算的规律

1. 和的模等于模的和

(a + b) \mod q = (a \mod q + b \mod q) \mod q

证明:

$(a+b) \mod q$ 的结果可以理解成长为 $a$ 与长为 $b$ 的木条拼接在一起得到长为 $a+b$ 的木条,然后用 $q$ 除得到的不足 $q$ 的部分的长度.相当于,先用长度为 $a$ 的木条除 $q$ 得到不足 $q$ 的部分 $a_1$ ,( $a \mod q$ ),然后用长度为 $b$ 的木条除 $q$ 得到不足 $q$ 的部分 $b_1$ ,( $b \mod q$ ),然后用 $a_1+b_1$ 拼成一个木条用 $q$ 除,得到剩余的部分, $(a_1+b_1) \mod q$ .显然这两种方法得到的结果是一样的.

(a_1+ a_2+\cdots + a_n) \mod q = ((( (a_1 \mod q) + a_2 ) \mod q + a_3 )\mod q + \cdots +a_n )\mod q

结论:显然全部加起来最后取模与边取模边加得到的结果是一样的.

2. 积的模等于模的积

(a \times b) \mod q = ( (a \mod q) \times (b \mod q)) \mod q

证明:

(a \times b) \mod q = ( (a \mod q) \times b) \mod q \tag{1}

所以根据 $(1)$ 和乘法交换律得到

\begin{align} ( (a \mod q) \times b) \mod q &= ( b \times (a \mod q)) \mod q \tag 2 \\ &= ( (b \mod q) \times (a \mod q)) \mod q \tag 3 \\ &=( (a \mod q) \times (b \mod q) ) \mod q \tag 4 \end{align}

结论:显然全部乘起来最后取模与边取模边乘得到的结果是一样的.

带余除法

一般地,设 $a,b$ 为整数,且 $b \ne 0$ ,则存在惟一的一对整数 $q$ 和 $r$ ,使得

a = b \cdot q + r , 0 \leqslant r < |b|.

转圈与取余的关系

如下图Figure 1所示:有 $8$ 个数: $0,1,2,\cdots,7$ 围成一个圈,问:

顺时针( $clockwise$ ),从 $0$ 开始走 $1$ 步是停下来是哪个位置?
顺时针( $clockwise$ ),从 $0$ 开始走 $4$ 步是停下来是哪个位置?
顺时针( $clockwise$ ),从 $0$ 开始走 $100$ 步是停下来是哪个位置?
顺时针( $clockwise$ ),从 $0$ 开始走 $x$ 步是停下来是哪个位置?
顺时针( $clockwise$ ),从 $7$ 开始走 $1$ 步是停下来是哪个位置?
顺时针( $clockwise$ ),从 $7$ 开始走 $2$ 步是停下来是哪个位置?
顺时针( $clockwise$ ),从 $7$ 开始走 $110$ 步是停下来是哪个位置?
顺时针( $clockwise$ ),从 $p(0 \leqslant p \leqslant 7)$ 开始走 $x$ 步是停下来是哪个位置?
逆时针( $Counterclockwise$ ),从 $0$ 开始走 $1$ 步是停下来是哪个位置?
逆时针( $Counterclockwise$ ),从 $0$ 开始走 $4$ 步是停下来是哪个位置?
逆时针( $Counterclockwise$ ),从 $0$ 开始走 $100$ 步是停下来是哪个位置?
逆时针( $Counterclockwise$ ),从 $0$ 开始走 $x$ 步是停下来是哪个位置?
逆时针( $Counterclockwise$ ),从 $p(0 \leqslant p \leqslant 7)$ 开始走 $x$ 步是停下来是哪个位置?

$circle1$

显然有一个很容易想到的规律1:从任意一个位置 $x$ 开始走,如果恰好走了一圈( $8$ 步),停下的位置就是 $x$ .

$\Rightarrow$ 走 $n(n \geqslant 0)$ 圈,相当于没有走
$\Rightarrow$ ,设一图长度(数字数量)为 $l$ ,走 $n \cdot l$ 步,相当于没有走,相当于,走了 $0$ 步
$\Rightarrow$ 走 $n \cdot l +1$ 步,相当于走了 $1$ 步

那么逆着走呢?

可以发现如下的规律,从某个位置逆着走 $1$ 步,所到达的位置与正着走 $7$ 步所到达的位置是一样的

所以: 从任意位置 $p$ 逆着走 $x(0 \leqslant x <8$ 步,所到达的位置与正着走 $8-x$ 步所到达的位置是一样的

由此可以得到:

顺时针( $clockwise$ ),从 $0$ 开始走 $1$ 步是停下来是哪个位置?
- $0+1=1$ ,到达位置 $1$
顺时针( $clockwise$ ),从 $0$ 开始走 $4$ 步是停下来是哪个位置?
- $0+4=4$ ,到达位置 $4$
顺时针( $clockwise$ ),从 $0$ 开始走 $100$ 步是停下来是哪个位置?
- $0+100 \% 8=5$ ,到达位置 $5$
顺时针( $clockwise$ ),从 $0$ 开始走 $x$ 步是停下来是哪个位置?
- $0+x\%8$ ,到达位置 $x \% 8$
顺时针( $clockwise$ ),从 $7$ 开始走 $1$ 步是停下来是哪个位置?
- $7+1\%8 = 8$ ,到达位置 $8$ , 但是没有位置 $8$ ,可知位置 $8$ 对应的就是位置 $0$ , $8 \% 8 = 0$
顺时针( $clockwise$ ),从 $7$ 开始走 $2$ 步是停下来是哪个位置?
- $(7+2\%8)\%8 = 1$ ,到达位置 $1$
顺时针( $clockwise$ ),从 $7$ 开始走 $110$ 步是停下来是哪个位置?
- $(7+110\%8)\%8 = 5$ ,到达位置 $5$
顺时针( $clockwise$ ),从 $p(0 \leqslant p \leqslant 7)$ 开始走 $x$ 步是停下来是哪个位置?
- $(p+x\%8)\%8$ ,到达位置 $(p+x \% 8)\%8$
逆时针( $Counterclockwise$ ),从 $0$ 开始走 $1$ 步是停下来是哪个位置?
- 逆走 $1$ 步,相当于正走 $7$ 步,到达 $7$
- 逆着走1,可以认为走了 $-1$ 步,-1%8=7
逆时针( $Counterclockwise$ ),从 $0$ 开始走 $4$ 步是停下来是哪个位置?
- 逆走 $4$ 步,相当于正走 $4$ 步,到达 $4$
- 逆着走 $4$ ,可以认为走了 $-4$ 步,-4%8=4
逆时针( $Counterclockwise$ ),从 $0$ 开始走 $100$ 步是停下来是哪个位置?
- 逆着走 $100$ ,可以认为走了 $-100$ 步,-100%8=4
- 到达位置 $4$
逆时针( $Counterclockwise$ ),从 $0$ 开始走 $x$ 步是停下来是哪个位置?
- $-x \% 8$
逆时针( $Counterclockwise$ ),从 $p(0 \leqslant p \leqslant 7)$ 开始走 $x$ 步是停下来是哪个位置?
- $(p - (x \% 8))\%8$

总结

在一个由 $n$ 个数字组成的圈中

规律1: 从任意一个位置 $x$ 顺时针走 $y$ 步,停下的位置为 $(x + y \% n ) \% n$ 规律2: 从任意一个位置 $x$ 逆时针走 $y$ 步,停下的位置为 $(x + (n- y \%n) ) \%n = (x+n -y\%n) \%n$

问题

注意下面图Figure 2,3,并不是从 $0$ 开始的,

问

Figure 1,从起点 $1$ 开始正走 $123$ 步,是哪里?
Figure 2,从起点 $2$ 开始正走 $124$ 步,是哪里?
Figure 1,从 $3$ 开始逆走 $132$ 步,是哪里?
Figure 2,从 $5$ 开始逆走 $124$ 步,是哪里?

$circle2$

$circle3$

余数

理解

c++中的取余