同余与模运算

66 阅读 0 评论 44 点赞

我是靠谱客的博主靓丽鸭子，最近开发中收集的这篇文章主要介绍同余与模运算，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

a mod b 表示 a 除以 b 的余数，在高级语言中表示成 a % b 。

int mod(int a,int b)
{
return a%b;
}

我们先记住下面几个公式：

1. (a+b) mod n=((a mod n)+(b mod n)) mod n

int add_mod(int a, int b, int n)
{
a %= n; b %= n;
return (int) ((long long)(a + b) % n);
}

2.(a−b) mod n=((a mod n)−(b mod n)+n) mod n
注意这里的 a mod n 可能会小于 b mod n ，则需要在结果上加上 n 。
```
int minus_mod(int a, int b, int n)
{
a %= n; b %= n;
return (int) ((long long)(a - b + n) % n);
}
```
- 3. ab mod n=(a mod n)(b mod n) mod n
  注意这里的 a mod n 和 b mod n 的乘积可能会溢出
```
int mul_mod(int a, int b, int n)
{
a %= n; b %= n;
return (int) ((long long)a * b % n);
}
```
大整数取模：

计算一下222222222222222222222222 mod 1234的结果，是否可以用下面的程序计算？
```
int mod(long long a, long long b)
{
return a%b;
}
```
它计算出来的结果是 441，可惜正确答案是1036
显然，我们能发现其中的错误在哪，因为long long的范围是9223372036854775807，所以一旦 a 大于long long的范围，那就肯定是错的。所以我们不能用整型来保存整数，要用字符数组来保存。

分析：

首先将大整数写成”自左向右“的形式，比如 1234=((1∗10+2)∗10+3)∗10+4 ，然后再用上面的公式1进行每步取模。
代码如下：
```
#include<cstdio>
#include<cstring>
using namespace std;
int main()
{
char n[100];
int m;
scanf("%s%d",n,&m);
int len = strlen(n);
int ans = 0;
for(int i=0; i<len; i++)
{
ans = (int)(((long long)ans*10 + n[i] - '0') % m);
}
printf("%dn",ans);
return 0;
}
```
这样再大的整数都没有问题。

幂取模：

如何计算出 abmodn 的值
我们可以使用上面的公式3，进行每步取模，因为 ab=a∗a∗a∗a∗a∗a∗...∗a 共有b个a相乘，每一次 ans = ans * a%n 即可。
```
int pow_mod(int a, int b, int n)
{
int ans = 1;
for(int i=0; i<b; i++)
{
ans = (int)((long long)ans * a % n);
}
return ans;
}
```
这里的时间复杂度就是 O(n) 了，但是如果b很大呢，所以我们需要优化一下：

这里采用二分法的思想。
比如 a14=(a7)2，a7=(a3)2∗a，a3=a2∗a
这样代码就是：
```
#include<cstdio>
using namespace std;
/*时间复杂度为O(logn)*/
int pow_mod(int a, int b, int n)
{
if(b == 0) return 1;
int x = pow_mod(a, b/2, n);
long long ans = (long long)x * x % n;
if(b%2 == 1) ans = ans * a % n;
return (int) ans;
}
int main()
{
int a,b,n;
scanf("%d%d%d",&a,&b,&n);
printf("%dn",pow_mod(a,b,n));
return 0;
} 
```
时间复杂度变成了 O(logn) 了。

模线性方程组

问题描述：输入正整数 a,b,n ，解方程 ax≡b(mod n) 。 a,b,n≤109 。

“ ≡ ”这个记号叫做同余， a≡b(mod n) 的含义是“ a 和 b 关于模 n 同余”，即 a mod n=b mod n 。所以我们可以推出 a≡b(mod n) 的充要条件是： a−b 是 n 的整数倍。

这样，原方程 ax≡b(mod n) ，可以理解为： ax−b 是 n 的整数倍。设倍数为 y，则 ax−b=ny ，移项得 ax−ny=b 。通过扩展欧几里得算法解出此方程。

特殊情况：
当 b=1 时， ax≡1(mod n) 的解称为 a 关于模 n 的逆。所以根据上面的分析， ax−ny=1 要有解，根据扩展欧几里得算法，1必须是 gcd(a,n) 的倍数，也就是说 gcd(a,n)=1 ，则 a 和 n 必须互素才会有解，并且只有唯一解。