同余定理

作者：blue

时间：2025.6.11

同余定理是数论里一个很实用的概念，简单来说：
如果两个整数 a 和 b，除以同一个整数 m（m≠0）后的余数相同，就称 a 和 b 对 m 同余，记作 a ≡ b (mod m)。

核心要点：

• 若 a ≡ b (mod m)，c ≡ d (mod m)，则：
  • 加减性：(a±c) ≡ (b±d) (mod m)

• 乘性：(a×c) ≡ (b×d) (mod m)

• 若 a ≡ b (mod m)，则有(a-b)%m==0，充要，反之依然成立

同余定理时常用来优化一些与前缀和相关的题目，下面我们来看几道例题：

P8649 [蓝桥杯 2017 省 B] k 倍区间 - 洛谷 (luogu.com.cn)

本题要求，求出数列中总共有多少个 K 倍区间吗，我们很容易想到，可以用前缀和来快速计算某个区间的和。

但是区间长度不固定，如何看每个区间来看它是不是k的倍数呢？

暴力解法很容易想到，枚举区间长度，然后以此长度，去枚举所有这个长度的区间，看其是不是k的倍数，时间复杂度为

O(n²)，代码如下：

#include <iostream>
using namespace std;
const int N=1e5+10;
int a[N];
int sum[N];
int main()
{
   
    int n,k;
    int ans=0;
    cin>>n>>k; 
    for(int i=1;i<=n;i++){
   
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
    }
    for(int i=1;i<=n;i++){
   
        for(int j=1;j<=n-i+1;j++){
   
            int t=sum[j+i-1]-sum[j-1];
            if(t%k==0) ans++;
        }
    }
    cout<<ans;
    return 0;
}

代码优化，O(n²)显然无法完全通过，这时同余定理出场，针对一个区间[i,j]，计算其是不是k倍区间的方法为

(sum[j]-sum[i-1])%k==0，则有sum[j]%k=sum[i-1]%k，所有我们可以计算出sum[0]~sum[n] mod k的余数，用hash表记录每个余数出现的次数，然后每个余数，从总数中任取两个（组合问题），即可计算出总共有多少个k倍区间，这个过程就相当于统计所有mod k余数相同的数，取出两个，有多少种取法，一种取法就是一个k倍区间。于是我们的时间复杂度，来到了O(n+k)，足以通过问题

#include <iostream>
#define int long long
using namespace std;
const int N=1e5+10;
int a[N];
int sum[N];
int h[N];
signed main(){
   
    int n,k;
    int ans=0;
    cin>>n>>k; 
    h[0]=1;//因为sum[0]%k==0所以要初始化为1 【所用前缀和数组的范围是sum[0]~sum[n]】 
    for(int i=1;i<=n;i++){
   
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
        h[sum[i]%k]++;
    }
    for(int i=0;i<=k;i++){
   
        ans+=(h[i]*(h[i]-1))/2;
    }
    cout<<ans;
    return 0;
}

P3131 [USACO16JAN] Subsequences Summing to Sevens S - 洛谷 (luogu.com.cn)

这道题，要求找出一个最长的区间，要求这个区间和 mod 7 为 0

依然用前缀和优化，然后我正序遍历前缀和数组，找到每一个余数最后一次出现的位置

倒序遍历前缀和数组，找到每一个余数第一次出现的位置

然后遍历余数，用其最后一次出现的位置，减第一次出现的位置，取最大值，即为最长区间

这里要注意为什么不用last-first，为什么不用+1

因为last-first，相当于是在计算这段区间的和，而sum[i]-sum[j-1] (位置上i-(j-1))，就已将暗含了+1

#include <iostream>
#include <cstring>
#define int long long
using namespace std;
const int N=5e4+10;
int a[N];
int sum[N];
int last[7];//mod7的余数，最后一次出现的位置 
int first[7];//mod7的余数，第一次出现的位置 
signed main()
{
   
    int n;
    int ans=0;
    memset(first,0x3f3f3f3f,sizeof(first));
    cin>>n;
    for(int i=1;i<=n;i++){
   
        cin>>a[i];
        sum[i]=(sum[i-1]+a[i])%7;
    } 
    for(int i=0;i<=n;i++){
   //正序遍历，找最后一次出现的位置 
        last[sum[i]]=i; 
    }
    for(int i=n;i>=0;i--){
   //倒序遍历，找第一次出现的位置 
        first[sum[i]]=i;
    } 
    for(int i=0;i<7;i++){
   
        ans=max(ans,last[i]-first[i]);
    } 
    cout<<ans;
    return 0;    
}

D - Pedometer (atcoder.jp)

接下来，看一道比较难的题目，本题是一道环形题（顺时针），要求求出两点间步数总和是m的倍数的个数。

针对这种环形题，首先要有的一个思路就是断环为链，ok这环形的问题就解决了

来看第二个要点，区间和，这个我们就用前缀和优化就行了，计算任意两点的距离（不能回到原点），我们最多用到

sum[2*n-2]，请读者自己根据题目样例，画图演示

所以我们很好想到暴力解法：

第一个循环，枚举起始点，第二个循环，枚举起始点开始走取别的点的步长最多n-1步（不能回到原点）

然后看区间和，是不是m倍区间，这很好理解

//暴力解法： 
for(int i=1;i<=n;i++){
   
    for(int j=1;j<=n-1;j++){
   
        int x=(sum[i+j-1]-sum[i-1])%m;
        if(x==0) ans++;
    }
}

优化解法：读到这里，读者就会想，这不就是第一题k倍区间吗，是的非常相似，但略有不同，不同在于断环为链之后

首先第一个循环：计算1号休息点到n号休息点，所需要用到sum[0]-sum[n-1]

这时统计方法为：

ans+=st[sum[i-1]];
st[sum[i-1]]++;

这个k倍区间并无不同（k倍区间那道题这样写也行），相当于每看一个sum，就看当前有多少个和这个sum余数相同的值，有多少个sum就贡献多少个m倍区间

但是第二个循环：就比较难理解，这相当于移动区间的最左端，第一个区间是1-n，现将末端移动到n+1，也就是回到了1，由于不能回到原点，所以1不能在这个新区间中，故而每前进一步，要消除最左侧的那个点的影响，故而st[sum[i-(n+1)]]--;

然后为什么不用加入当前点的影响呢？请读者设想，假设：若我加入了当前点的影响（比如这里加入n+1点的影响），在计算n+2时，若n+1到n+2组成一个m倍区间，则这个结果就会被我们所统计，但实际上这就是1->2，这个结果在我们第一次循环计算1号休息点到n号休息点，就已经计算过了，属于重复计算。

广义上来讲，加入这节点的影响，只对后续节点有贡献，而这个节点对后续节点的贡献，我在第一次循环就统计过了，故而不用再次统计，所以第二个循环中，只用移除最左端的影响（因为不能回到原点），不用增加当前点的影响。

故而代码如下：

for(int i=n+1;i<=2*n-1;i++){
   
    st[sum[i-(n+1)]]--;
    ans+=st[sum[i-1]];
}

ACcode：

#include <iostream>
#include <cstring>
#define int long long
using namespace std;
const int N=2e5+10;
const int M=1e6+10;
int a[2*N];
int sum[2*N];
int st[M];
signed main()
{
   
    int n,m;
    int ans=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
   //断环为链
        cin>>a[i];
        if(i!=n) a[i+n]=a[i];
    }
    for(int i=1;i<2*n-1;i++){
   
        sum[i]=(sum[i-1]+a[i])%m; 
    }
    for(int i=1;i<=n;i++){
   //计算1号休息点到n号休息点，所需要用到sum[0]-sum[n-1]
        ans+=st[sum[i-1]];
        st[sum[i-1]]++;
    }
    for(int i=n+1;i<=2*n-1;i++){
   //移动区间末尾，区间长度保持
        st[sum[i-(n+1)]]--;
        ans+=st[sum[i-1]];
    }
    cout<<ans;
    return 0;
}