1、模运算概述

给定一个正整数p，和任意一个整数n，一定存在等式n=k*p + r。其中k、r是整数，并且满足0<=r

模运算有如下性质： ①若p|(a-b)(意思是p能整除(a-b))，则a≡b (mod p)。例如 11 ≡ 4 (mod 7)， 18 ≡ 4(mod 7) ②(a mod p) = (b mod p),那么a≡b (mod p) ③对称性：a≡b (mod p)等价于b≡a (mod p) ④传递性：若a≡b (modp)且b≡c (% p) ，则a≡c (modp) 运算规则 模运算与基本四则运算有些相似，但是除法例外。其规则如下： (a + b) % p = (a % p + b % p) % p （1） (a - b) % p = (a % p - b % p) % p （2） (a * b) % p = (a % p * b % p) % p （3） (a^b) % p = ((a % p)^b) % p （4） 结合律： ((a+b) % p + c) % p = (a + (b+c) % p) % p （5） ((a*b) % p * c)% p = (a * b*c) % p （6）// (a%p*b)%p=(a*b)%p 交换律： (a + b) % p = (b+a) % p （7） (a * b) % p = (b * a) % p （8） 分配律： ((a +b)% p * c) % p = ((a * c) % p + (b * c) % p) % p （9）

2、模运算判别奇偶数

如果一个整数n，对2求模，如果余数为0，则是偶数，否则为奇数。 int odd_even(int a) { return (a % 2); }

3、模运算判断素数

如果一个数只能分解为1和它本身相乘，我们称该数为素数(或质数)，例如：2、3、5、7是素数，4、6、8、10

判断一个数是否为素数的方法是试除法：最基本的试除法是，对于要判断的数n，如果n除以比n小的大于1的每

int prime_num(int a) { int cout = sqrt(a); for (; cout > 1;cout--) { if ((a % cout) == 0) return 0; } return 1; }

4、模运算求解最大公约数

给定两个整数a、b，如果d既是a的约数也是b的约数，那么d就是a、b的公约数，如果d是所有公约数中最大的，

a可以表示成:a=kb + r ，r=a mod b, 假设d是a、b的公约数，则a=k1*d，b=k2 * d，将a、b代入上式得k1*d = k*k2 * d + （a mod b），即（a mod 

int gcd(int a, int b) { if (b != 0) return gcd(b, a % b); return a; }

4模运算求解最大