数论基础一一同余定理

简介: 同余定理是数论中的重要概念,用于判断两数对同一模数的余数是否相同,记作 \(a \equiv b \ (\text{mod } m)\)。其核心性质包括加减性和乘性,广泛应用于优化前缀和相关问题。本文通过三道例题详细解析同余定理的应用:1)蓝“k倍区间”,利用哈希表记录余数出现次数,将时间复杂度从 \(O(n^2)\) 降至 \(O(n+k)\);2)题“Subsequences Summing to Sevens S”,通过正序与倒序遍历寻找最长区间;3)AtCoder D题“Pedometer”,断环为链结合同余定理解决环形步数统计问题。这些实例展示了同余定理在算法竞赛中的高效应用。

同余定理

作者: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;
}
目录
相关文章
|
Python
python自动生成含样式的Excel表格数据案例
python自动生成含样式的Excel表格数据案例
847 1
|
10月前
|
人工智能 JSON 搜索推荐
如何创建GS1Digital Link产品全生命周期管理二维码
GS1 Digital Link是GS1推出的创新标准,将传统条码(如GTIN)升级为可联网的结构化URL二维码,支持GTIN、批次、序列号等信息编码。扫码即可跳转至官网、溯源平台或获取JSON/RDF数据,实现产品全生命周期数字化管理与多场景智能响应。
1054 2
|
存储 网络协议 容灾
降低存储网络55% 延迟!阿里云存储论文入选计算机顶会
凭借在规模化部署和应用模型上的创新,阿里云存储团队发表的技术论文《Deploying User-space TCP at Cloud Scale with LUNA》被 USENIX ATC'23 收录。
2196 4
降低存储网络55% 延迟!阿里云存储论文入选计算机顶会
|
机器人 API 定位技术
具身智能干货|ROS2理论与实践系列(二):ROS2通信机制核心
机器人是一种高度复杂的系统性实现,一个完整的机器人应用程序可能由若干功能模块组成,每个功能模块可能又包含若干功能点,在不同功能模块、不同功能点之间需要频繁的进行数据交互。比如以导航中的路径规划模块为例: 路径规划时就需要其他功能模块输入数据,并输出数据以被其他模块调用。 输入的数据有地图服务提供的地图数据、定位模块提供的机器人位姿数据、人机交互模块提供的目标点数据......。 输出的路径信息则被运动控制订阅或是回显在人机交互界面上。 那么这些相对独立的功能模块或功能点之间是如何实现数据交互的呢?在此,我们就需要介绍一下ROS2中的通信机制了。
3340 62
|
NoSQL 关系型数据库 MySQL
阿里云PolarDB游戏场景最佳实践
阿里云PolarDB游戏场景最佳实践涵盖了数据库体系演进、行业优化、Redis解决方案、性能优化、备份还原及全球部署等内容。PolarDB通过共享存储、物理复制等技术提升读扩展和大容量支持,针对游戏行业的高IO需求进行优化,提供秒级备份与快速恢复能力。同时,PolarDB for Redis实现了一写多读架构,支持百TB级别的高性能存储,具备成本优势。该方案已在米哈游等大型游戏中广泛应用,确保了高并发下的稳定性和数据一致性,满足游戏行业的特殊需求。
935 36
|
安全 Java 数据安全/隐私保护
Spring Security: 深入解析 AuthenticationSuccessHandler
本文深入解析了 Spring Security 中的 `AuthenticationSuccessHandler` 接口,它用于处理用户认证成功后的逻辑。通过实现该接口,开发者可自定义页面跳转、日志记录等功能。文章详细讲解了接口方法参数及使用场景,并提供了一个根据用户角色动态跳转页面的示例。结合 Spring Security 配置,展示了如何注册自定义的成功处理器,帮助开发者灵活应对认证后的多样化需求。
623 2
|
存储 缓存 搜索推荐
HTTP500代码怎么解决?常见的5xx网页错误及其原因
本文介绍了如何修复HTTP 500错误及常见的5xx网页错误。500错误表示服务器无法处理请求,可能由文件权限、脚本错误、数据库连接或配置问题引起。作为用户,可尝试重新加载页面、检查URL或清除缓存;作为网站所有者,需检查`.htaccess`文件、服务器日志、插件冲突及PHP版本等。此外,文章还列举了其他5xx错误(如502、503、504等)及其原因,帮助定位和解决服务器端问题,避免影响流量与搜索引擎排名。
12178 4
|
API 开发者 Python
Pygame Zero(pgzrun)详解(简介、使用方法、坐标系、目录结构、语法参数、安装、实例解释)
Pygame Zero(pgzrun)详解(简介、使用方法、坐标系、目录结构、语法参数、安装、实例解释)
3860 17
|
机器学习/深度学习 并行计算 异构计算
WINDOWS安装eiseg遇到的问题和解决方法
通过本文的详细步骤和问题解决方法,希望能帮助你顺利在 Windows 系统上安装和运行 EISeg。
1099 2