最近做算法题的时候，又用到了余数定理，之前做Leetcode的时候，做过一道**连续子数组和**的时候，就用到了同余定理。因此在此做一下总结。

余数的加法定理

a 与b的和除以c的余数，等于a,b分别除以c的余数之和，或这个和除以c的余数。
$$
(a+b) % c = a%c + b%c
$$
当余数的和比除数大时，所求的余数等于余数之和再除以c的余数。

余数的乘法定理

a与b的乘积除以c的余数，等于a,b分别除以c的余数的积，或者这个积除以c所得的余数。
$$
(ab)%c = (a%c)(b%c)
$$
例如：
$$
23%5 = 3;16%5=1 \Longrightarrow (2316)%5 = 31=3
$$
当余数的和比除数大时，所求的余数等于余数之积再除以的余数。

这个定理的一个应用就是，大数幂取余。

最近做的一道题是，给了三个数，比如 m，n，k。求$ (m^n)%k$。

看似很简单，用java实现的话。如下：

1
double res = Math.pow(m, n) % k;

但是，如果$m=4296,n=1601,k=4757的话，m^n将是非常大的数，超过了计算机能够表示的上限。$

1
double res = Math.pow(4096, 1601)//Infinity

因此就不能使用这么简单的方法，于是就用到了余数的乘法定理。

$ m^n = (mmm…)$

因此
$$
(mmm…)%k = (m*…(m(m%k)%k)%k…)%k
$$
代码实现如下：

1
2
3
4
5
6
7
8
9
public class Solution {
    public int Dcrypt(int m,int n,int k){
        int res = m%k;
        for (int i = 0; i < n-1; i++) {
            res = (res*m)%k;
        }
        return res;
    }
}

$4296^{1601}%4757=228$

同余定理

若两个整数a、b被自然数m除有相同的余数，那么称a、b对于模m同余。
若两个数a，b除以同一个数m得到的余数相同，则a, b的差一定能被m整除。

即
$$
a%m = b%m\Longrightarrow(a-b)%m=0
$$
也就是说$a-b 是 m的倍数$

连续的子数组和

给你一个整数数组nums和一个整数 k ，编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组：

  • 子数组大小 至少为 2 ，且
  • 子数组元素总和为 k 的倍数。

如果存在，返回 true ；否则，返回 false 。

如果存在一个整数 n ，令整数 x 符合 x = n * k ，则称 x 是 k 的一个倍数。0 始终视为 k 的一个倍数。

示例1：

输入：nums = [23,2,4,6,7], k = 6
输出：true
解释：[2,4] 是一个大小为 2 的子数组，并且和为 6 。

示例2：

输入：nums = [23,2,6,4,7], k = 6
输出：true
解释：[23, 2, 6, 4, 7] 是大小为 5 的子数组，并且和为 42 。
42 是 6 的倍数，因为 42 = 7 * 6 且 7 是一个整数。

示例3：

输入：nums = [23,2,6,4,7], k = 13
输出：false

一般看到连续子数组，都会想到**数组前缀和。这道题可以用暴力二重循环解，但是会超时**。

如果要在O(n)时间复杂度内解决，只能采用空间换时间的想法啦！

用哈希表来存储，数组前缀和与k的余数。key为余数，value为数组前缀和长度【数组下标】

使用同余定理，如果 某一前缀和%k 所得余数 存在于哈希表中，那么说明 找到了同余。

此时可以确定存在子数组的和是k的倍数。然后判断长度是否小于2，这就用到了value了。

下面我们用图解说明吧

拿nums = [23,2,4,6,7], k = 6举例吧

初始如下

image-20220908113437512

然后遍历数组，计算前缀和以及取余

image-20220908113750934

前缀和为23，$23%6=5$，哈希表没有余数5，不存在同余。所以存入哈希表中。

image-20220908114026587

前缀和为25，$25%6=1$，哈希表没有余数1，不存在同余。所以存入哈希表中。

image-20220908114438178

前缀和为29，$29%6=5$，哈希表中存在余数5。即存在同余。

image-20220908115255437

这两个前缀和数组，具有相同的余数。
$$
23%6=5 \ and \ 29%6=5
$$
则
$$
(29-23)%6=0
$$
则子数组 [2,4]之和即为6的倍数。长度为 $2-0=2$。满足条件。

因此返回true。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>(nums.length);
        map.put(0,-1);						//初始化哈希表
        int sum = 0;						//记录前缀和
        for (int i = 0; i < nums.length; i++) {
            sum+=nums[i];//前缀和
            int x = sum % k;//取余
            if(map.containsKey(x))
                if(i-map.get(x)>=2)return true;//i-map.get(x)计算子数组长度
            }else map.put(x,i);
        }
        return false;
    }
}

__END__