求余：
取整除后的余数。例如：
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>usingnamespacestd;intmain(){inta = -1;intb = 26;intc = 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>usingnamespacestd;intmain(){inta = -1;intb = 26;intc = 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 bY1 := 0Y2 := 1B := bA := aQ := 最近一个小于或等于 B / A 的整数R := B - Q * A当 R > 0 循环Temp := Y1 - Y2 * Q如果 Temp 大于等于 0 则Temp := Temp mod b否则Temp := b - ((-Temp) mod b)Y1 := Y2Y2 := TempA := BB := RQ := 最近一个小于或等于 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 | publicstaticinteuclideEtendu(inta, intp){intn0 = p;intb0 = a;intt0 = 0;intt=1;intq = n0/b0;intr=n0-q*b0;inttemp = 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;}returnt;} |