【算法】同余定理及快速幂求模

港控/mmm° 2022-04-01 10:00 372阅读 0赞

### 文章目录 ###

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

#### 定义及其性质 ####

**定以**  
数论中的重要概念。给定一个正整数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<stdio.h>//大数求余，其中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] != '\0'; i++)
    			m = ((m*10)%n + (a[i] - '0')%n)%n;
    		printf("%d\n", m);               //输出求得的mod值
    	}
    return 0;
    }

这是在10进制下的做法，千进制也同理，\* 10改为 \* 1000就可以了

--------------------

#### 快速幂取模(次方求模) ####

对次方数求模一般方法需要试除法，运行较慢或者a，b超出计算机存储范围  
对于511的指数11可以变为2进制数1011即  
11 = 1 \* 23 \+0 \* 22\+1 \* 21\+1 \* 20  
则511可转化为58\*52\*51  
运用公式 (a \* b) % m = ((a % m) \* (b % m)) % m  
**代码实现(函数部分)**

int fun(int a, int b， int mode)   //a为底数，b为指数的二进制形式，mode为除数
    { 
    	int sum = 1;//sum用于记录取模结果
    	while(b != 0)
    	{ 
    		if(b&1) //用于判断b的末位是否为1
    		{ 
    			sum = (sum*a)%mode;  
    			b--;	
    		}
    		a = (a*a)%mode; //底数的1次方，2次方依次……变化
    		b /= 2;//去掉上一位(二进制中) 
    	}                       
    	return sum;
    }

&是C的位运算符的一种，进行逻辑与运算，格式是：变量1&变量2，进行计算时，将会把类型提升为int。二进制运算符&通过对两个操作数一位一位的比较产生一个新的值，对于每个位，只有两个操作数的对应位都为1时结果才为1.如10000001&11000000的结果为“10000000”

--------------------