关于求模和求余-求余: 取整除后的余数。例如: 10 MOD 4=2; -17 MOD 4=-1; -3 MOD 4=-3; 4 MOD (-3)=1; -4 MOD 3=-1 如果有a MOD b是异号,那么得出的结果符号与a相同;当然了,a MOD b就相当于a-(a DIV B ) *b的运算。例如: 13 MOD 4=13-(13 DIV 4)*4=13-12=1 求模:
转载:http://www.allopopo.cn/?p=269
规定“a MOD b”的b不能为负数
分三种情况来处理 a mod b 计算
a 和 b 均为正整数
当 a 和 b 均为正整数时,a mod b 实为求余运算。
(i)当a>b时,不断从a中减去b,直到出现了一个小于b的非负数。
例如: 8 MOD 3=2
(ii)当a<b时,结果为a。如:
3 MOD 8=3
a 为负整数
当 a 为负整数时,稍微麻烦点。例如 -1 mod 26,写个程序测试一下:
1
2
3
4
5
6
7
8
9
10
|
#include <iostream> using namespace std;
int main(){
int a = -1;
int b = 26;
int c = a % b;
cout << c << endl;
} |
得到的结果是 -1,但是实际运算结果应当为 25。用 Java 写了个程序,运算结果也是一样的,也是 -1。这是因为无论是 C++ 还是 Java 都不处理同余的情况。即两个整数除以同一整数,余数相同,则两数同余。既然我们不知道如何直接对负数求模,那找到这个负数同余的正整数便可以了。
要计算 c = a mod b,其中 a 为负数,要找得与 a 同余的正整数,只需要再在 a 的基础上,再 + b 即可。写成代码就是:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
#include <iostream> using namespace std;
int main(){
int a = -1;
int b = 26;
int c = a % b;
if (c < 0){
cout << (c + b) << endl;
} else {
cout << c << endl;
}
} |
分数求模
最后这个最麻烦点,是分数求模运算。因为服务器不支持 LaTeX,所以只能用比较粗糙的数学书写格式,^{} 用于上标,而 _{} 则是下标。
要计算 a^{-1} mod b,也称为对 b 求 a 的反模。我们需要寻找 c,使得 c * a mod b = 1。例如 1/4 mod 9 = 7,因为 7 * 4 = 28,28 mod 9 = 1。并且只有当 a 和 b 的最大公约数为 1 时,此反模才存在。
为了对分数求模,我们需要使用欧几里德扩展算法。逐步推进,从步骤 0 开始,在步骤 i 求得的商标记为 Q_{i}。除以以外,每个步骤还需要计算一个临时的量,标记为 Y_{i},Y_{0} 和 Y_{1} 已经给出,分别是 0 和 1。再往后的计算当中,每次循环,更新 Y_{i} = Y_{i-2}- Y_{i-1} * Q_{i-2} mod b。循环从 b 除以 a 开始:
假设我们要对 26 求 15 的反模,也就是 1/15 mod 26。
步骤 0 | 26 = 01 * 15 + 11 | Y_{0} = 0 |
步骤 1 | 15 = 01 * 11 + 04 | Y_{1} = 1 |
步骤 2 | 11 = 02 * 04 + 03 | Y_{2} = Y_{0} – Y_{1} * Q_{0} mod 26 = 00 – 01 * 01 mod 26 = 25 |
步骤 3 | 04 = 01 * 03 + 01 | Y_{3} = Y_{1} – Y_{2} * Q_{1} mod 26 = 01 – 25 * 01 mod 26 = 02 |
步骤 4 | 03 = 03 * 01 + 00 | Y_{4} = Y_{2} – Y_{3} * Q_{2} mod 26 = 25 – 02 * 02 mod 26 = 21 |
Y_{5} = Y_{3} – Y_{4} * Q_{3} mod 26 = 02 – 21 * 01 mod 26 = 07 |
如果最后一个非零余数出现在第 k 步骤,且余数为 1,则反模存在,且为 Y_{k+2}。在我们这个例子当中,最后一个非零余数出现在步骤 3,且此余数为 1,所以对 26 求 15 的反模,应当为 Y_{5} = 7。由此,最后得出 1/15 mod 26 = 7。
最后列出分数求模的算法:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
// 求 a^{-1} mod b Y1 := 0 Y2 := 1 B := b A := a Q := 最近一个小于或等于 B / A 的整数 R := B - Q * A 当 R > 0 循环 Temp := Y1 - Y2 * Q
如果 Temp 大于等于 0 则
Temp := Temp mod b
否则
Temp := b - ((-Temp) mod b)
Y1 := Y2
Y2 := Temp
A := B
B := R
Q := 最近一个小于或等于 B / A 的整数
R := B - Q * A
循环末 如果 bo 不等于 1 则 b 不具有针对 n 的反模。 否则返回 Y2。 |
翻译成 Java 方法如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
public static int euclideEtendu( int a, int p)
{ int n0 = p;
int b0 = a;
int t0 = 0 ;
int t= 1 ;
int q = n0/b0;
int r=n0-q*b0;
int temp = 0 ;
System.out.println( "=>Calculation of " + a + "^-1 mod " + p + " using Extended Euclidean Algorithm" );
while (r> 0 )
{
temp = t0-q*t;
if (temp>= 0 ){
temp = temp % p;
} else {
temp = p-(-temp % p);
}
t0=t;
t=temp;
n0=b0;
b0=r;
q=(n0/b0);
r=n0-q*b0;
}
if (b0!= 1 ){
System.out.println(a + " doesn't have inverse modulo of " + p);
t=- 1 ;
}
return t;
} |
上一篇: 我的猫 - 分片教程:分片规则与范围求模算法详解 | 学习笔记
下一篇: 模运算
推荐阅读
-
数的机器码表示:原码、反码、补码、变形补码、移码和浮点数编码-数学定义:例:+111的原码为0111,-101的原码为1101 (2) 纯小数的原码表示 纯小数的原码首位同样为符号位,后面的数值则表示小数的尾数,纯小数的整数位为默认为0无需表示。 例:+0.111的原码为0111,-0.101的原码为1101 可以看到,+111和+0.111的原码同为0111,这是因为约定的小数点位置不同,整数的原码的小数点约定在末尾,纯小数的原码的小数点约定在数值的最前面,这样通过约定小数点的位置来表示数的方法就称为定点数表示法,约定小数点位置实际上就是约定编码中每一位的权重。 二、反码 正数的反码与其原码相同。 负数的反码是其对应原码的符号位不变,数值位按位取反。 数学定义:例: 真值 +111 -101 +0.111 -0.101 原码 0111 1101 0111 1101 反码 0111 1010 0111 1010 三、补码 原码虽然转换很简单,但是在做减法时操作很复杂(减不够还要借位),因此计算机在做加负数操作时会先将负数的原码转换为补码再做加法。 先举个栗子,假设时钟现在是9点钟,我把时针往回拨3个小时是6点钟,或者顺时针往后拨9个小时还是6点钟,也就是说9-3的结果等同于9+9(mod 12),对于模数12,-3的补码为+9,这就引申出了一种将减法转换为加法的思想,把减去一个正数视为加上一个负数(例如9+(-3)),再将负数转换为对应的补码,最后就可以和补码做加法了,若结果超出了模数则丢弃一个模数即可。 如图所示:9减去灰色的部分(-3)就等同于加上蓝色的部分,即-3的补码即为蓝色部分的长度9(mod 12)。即补码=模数+真值(超出模数则舍弃一个模数) (1) 整数的补码表示 对于一个n位的二进制真值x,则取模数为2^(n+1),若x为正数则补码和原码相同(加上一个模数又需舍弃一个模数 故相同),若为负数则补码为模数加上x。相对于原码,补码这里的首位就不仅代表原数真值的符号了,也是补码自己的一个数值位。 取模数为2^(n+1)是因为在需要舍弃模数时只需要舍弃运算结果(二进制数)的最高位即可,这在计算机中很容易实现 数学定义:例:三位二进制数的模数2^4就是10000,故+111的补码为0111(即10000 + 111 = 0111 (舍弃模数位)),-101的补码为1011(即10000 - 101 = 1011) 补码运算示例:那么+111 - 101 = +111 + (-101) = 0111 + 1011 = 10010,运算结果只保留后四位(即舍弃模数位),故计算结果为0010。这样就通过加法实现了减法运算。 补码可表示数据范围:由数学定义可知,n位二进制补码可表示的数据范围为 -2n-1~2n-1-1。以8位的byte类型数为例,可表示的数据范围为 -27~27-1,即-128至+127,最小负数-128(补码:1000 0000),最大负数-1(补码:1111 1111),0(补码:0000 0000),最小正数1(补码:0000 0001),最大正数127(补码:0111 1111)。 由补码求真值:正数的补码即为原码即为真值,负数的真值由计算规则可知 负数真值= - (模数 - 补码),以补码1111 1111为例,其真值 = - (1 0000 0000 - 1111 1111) = - 0000 0001 = -1 (2) 纯小数的补码表示 对于一个纯小数x,则取模数为2^1,正数的补码和原码相同,负数的补码为模数2加上x。同样补码的首位不仅代表原数真值的符号,也是补码的数值位。 数学定义:例:纯小数的模数2就是10,故+0.111的补码为0111,-0.101的补码为1011(小数点约定在符号位后) 计算机中求补码的规则 可以注意到求负数的补码时还是要做减法,这在计算机中就很不方便了,但是通过其数学定义可以看到无论是整数还是纯小数,负数的补码都等于反码的末尾加1,而这又等同于原码数值位从右向左遇到第一个1后,这个1左边的数值位都按位取反,故实际计算机中求补码的规则如下:正数的补码等于原码负数的补码等于原码的数值位从右向左的第一个1左边的所有数值位按位取反(例:byte类型值-6的原码为1000 0110,则其补码为1111 1010) 四、变形补码 两个补码在运算时可能会溢出从而产生错误的结果,比如0111+0101 = 1100,两个正数相加反而得到了一个负数,那么在计算机中要如何判断运算结果是否溢出了呢,这就引申出了变形补码。从直观上看,相对于补码来说变形补码就是用两位来表示符号位,00表示正数,11表示负数。运算结果符号位为01表示正溢出,10表示负溢出。
-
关于求模和求余-求余: 取整除后的余数。例如: 10 MOD 4=2; -17 MOD 4=-1; -3 MOD 4=-3; 4 MOD (-3)=1; -4 MOD 3=-1 如果有a MOD b是异号,那么得出的结果符号与a相同;当然了,a MOD b就相当于a-(a DIV B ) *b的运算。例如: 13 MOD 4=13-(13 DIV 4)*4=13-12=1 求模: