文章目录

• 定义及其性质
• 大数的高精度对单精度取模
• 快速幂取模(次方求模)

定义及其性质

定以
数论中的重要概念。给定一个正整数m，如果两个整数a和b满足a-b能够被m整除，即m/(a-b)得到一个整数，那么就称整数a与b对模m同余，记作a≡b(mod m)。对模m同余是整数的一个等价关系。 两个整数a、b，若它们除以整数m所得的余数相等，则称a与b对于模m同余或a同余于b模m。
性质
1.反身性：a≡a (mod m)；
2.对称性：若a≡b(mod m)，则b≡a (mod m)；
3.传递性：若a≡b(mod m)，b≡c(mod m)，则a≡c(mod m)；
4.同余式相加：若a≡b(mod m)，c≡d(mod m)，则a±c≡b±d(mod m)；
5.同余式相乘：若a≡b(mod m)，c≡d(mod m)，则ac≡bd(mod m)。
6.幂运算：如果 a≡b(mod m)，那么an≡bn(mod m)；
7.除法：若 ac≡bc(mod m)，c≠0则 a≡b(mod m/gcd(c,m))，其中gcd(c,m)表示c和m的最大公约数，
8.若a≡b(mod mi)，(i=1,2…n) 则a≡b(mod [m1,m2,…mn]) ，其中[m1,m2,…mn] 表示m1,m2,…mn的最小公倍数。
应用

(a + b) % m = (a % m + b % m) % m

设 a = k1 * m + r1，b = k2 * m + r2
则 (a + b) % m = ((k1 * m + r1) + (k2 * m + r2)) % m
= ((k1 + k2) * m + (r1 + r2)) % m
= (r1 + r2) % m
= (a % m + b % m) % m
所以 (a + b) % m = (a % m + b % m) % m

(a * b) % m = ((a % m) * (b % m)) % m

设 a = k1 * m + r1，b = k2 * m + r2
则 (a * b) % m = ((k1 * m + r1) * (k2 * m + r2)) % m
= (k1 * k2 * m^2 + (k1 * r2 + k2 * r1) * m + r1 * r2) % m
= (r1 * r2) % m
= ((a % m) * (b % m)) % m
所以 (a * b) % m = ((a % m) * (b % m)) % m

---

大数的高精度对单精度取模

大数在编程中表示超过32位二进制位的数，不能直接求模，只能对其“分块”求模

应用公式(a + b) % m = (a % m + b % m) % m可做到边运算边取余
一个高精度数对一个数取余，可以把高精度数看成各位数的权值与个位数乘积的和。
比如1234 = ((1 * 10 + 2) * 10 + 3) * 10 + 4，对这个数进行取余运算就是上面基本加和乘的应用每步求模得1234%n = ((((1 * 10)%n+2%n)%n * 10%n+3%n)%n * 10%n+4%n)%n
代码实现 #include//大数求余，其中n为除数 ，数组a[]用于存大数 char a[1000]; int main() int i,j,k,m,n; { while(scanf("%s%d",a , &n) != EOF) { m=0; for(i=0; a[i] != '