模运算的艺术:从基础到高阶的算法竞赛应用

        在算法竞赛中,模运算(取模运算)是一个非常重要的概念,尤其在处理大数、防止溢出、以及解决与周期性相关的问题时。C++ 中的模运算使用 % 运算符,但它的行为和使用场景需要特别注意。

1. 模运算的基本概念

模运算是指求一个数除以另一个数的余数。在 C++ 中,模运算使用 % 运算符。例如:

int a = 17;
int b = 5;
int result = a % b; // result = 2,因为 17 除以 5 的余数是 2

2. 模运算的性质

模运算有一些重要的性质,这些性质在算法竞赛中经常被用到:

  • 结合律:

  • 分配律:

  • 幂运算的模:

3. 模运算的应用场景

3.1 防止整数溢出

        在算法竞赛中,经常会遇到大数运算,直接计算可能会导致整数溢出。使用模运算可以有效地防止溢出。

例如,计算 (a×b)%m时,可以先对 a和 b分别取模,然后再相乘取模:

long long a = 123456789;
long long b = 987654321;
long long m = 1000000007;
long long result = (a % m) * (b % m) % m;

3.2 周期性问题的处理

        模运算常用于处理周期性或循环性质的问题。例如,计算某个数在模 m 下的性质,或者判断两个数在模 m 下是否相等。(同余定理)

3.3 快速幂算法

        快速幂算法(Exponentiation by Squaring)是一种高效计算大数幂模的方法。通过递归或迭代的方式,可以将时间复杂度从 O(n) 降低到 O(log⁡n)。

long long fast_pow(long long base, long long exp, long long mod) {long long result = 1;while (exp > 0) {if (exp % 2 == 1) {result = (result * base) % mod;}base = (base * base) % mod;exp /= 2;}return result;
}

3.4 组合数学中的模运算

        在组合数学中,模运算常用于计算组合数、排列数等。由于组合数可能非常大,通常会使用模运算来限制结果的大小。

例如,计算组合数 C(n,k)%m时,可以使用递推公式或预处理阶乘和逆阶乘的方法。

4. 负数的模运算

在 C++ 中,计算规则是:先按正整数求余,然后加上符号,模运算的结果符号与被除数相同例如:

int a = -17;
int b = 5;
int result = a % b; // result = -2,因为 -17 除以 5 的余数是 -2

如果需要得到非负的余数,可以手动调整:(非常重要)

int mod(int a, int m) {return (a % m + m) % m;
}

5. 模运算的常见错误

  • 除数为零:模运算的除数不能为零,否则会导致运行时错误。

  • 负数模运算:需要注意负数的模运算结果可能不符合预期,需要手动调整。

  • 溢出问题:即使使用了模运算,仍然需要注意中间结果的溢出问题。

6.取模操作满足以下性质

(1)加:(a+b)%m=((a%m)+(b&m))%m。如果没有限制a、b的正负,在C代码中的左右可能符号相反、大小相差m。

(2)减:(a-b)%m=((a%m)-(b&m))%m。在C代码中左右可能符号相反、大小相差m。

(3)乘:(a*b)%m=((a%m)*(b&m))%m。

(4)然而,对除法取模进行类似操作是错误的:(a/b)%m=((a%m)/(b&m))%m。

例如,(100/50)%20=2,(100%20)/(50%20)%20=0,两者不相等。

1. 加法取模:(a+b)%m=((a%m)+(b%m))%m

问题描述

如果没有限制 aa 和 bb 的正负,在 C++ 中,左右两边的结果可能符号相反、大小相差 mm。

原因分析

在 C++ 中,模运算 % 的结果符号与被除数相同。例如:

  • 7%5=2

  • −7%5=−2

        因此,如果 a 或 b 是负数,a%m 或 b%m 的结果可能是负数。当两个负数相加时,结果可能超出模数 m 的范围,导致最终结果符号相反或大小相差 m。

解决方法

为了保证结果非负,可以在最终结果上加上 m 再取模:

int mod_add(int a, int b, int m) {return ((a % m) + (b % m) + m) % m;
}

2. 减法取模:(a−b)%m=((a%m)−(b%m))%m

问题描述

在 C++ 中,左右两边的结果可能符号相反、大小相差 m。

原因分析

        与加法类似,如果 a%m或 b%m 是负数,减法结果可能超出模数 m 的范围,导致最终结果符号相反或大小相差 m。

解决方法

为了保证结果非负,可以在最终结果上加上 m 再取模:

int mod_sub(int a, int b, int m) {return ((a % m) - (b % m) + m) % m;
}

3. 乘法取模:(a×b)%m=((a%m)×(b%m))%m

问题描述

乘法取模的性质在 C++ 中成立,但需要注意中间结果可能溢出。

原因分析

乘法取模的性质是基于模运算的结合律和分配律的,因此在 C++ 中成立。但如果 a 和 b 较大,直接计算 (a%m)×(b%m)可能会导致溢出。

解决方法

使用更大的数据类型(如 long long)来存储中间结果,或者分步计算:

int mod_mul(int a, int b, int m) {return ((long long)(a % m) * (b % m)) % m;
}

4. 除法取模:(a/b)%m≠((a%m)/(b%m))%m

问题描述

除法取模的性质在 C++ 中不成立。

原因分析

除法取模的性质不成立的原因是:

  • 除法运算 a/b 的结果与模运算 a%m 和 b%m 没有直接关系。

  • 模运算会丢失部分信息,导致除法结果无法正确反映。

解决方法

        在模运算中,除法需要通过乘法逆元来实现。如果 mm 是质数,可以使用费马小定理计算逆元:(a/b)%m=(a×b−1)%m

其中 b−1 是 b 的模 m 逆元。

代码实现

// 快速幂算法计算逆元
long long inv(long long b, long long m) {return fast_pow(b, m - 2, m);
}// 除法取模
int mod_div(int a, int b, int m) {return ((long long)(a % m) * inv(b, m)) % m;
}

7. 模运算的优化技巧

  • 预处理:在需要多次进行模运算的情况下,可以预处理一些中间结果,减少重复计算。

  • 位运算:在某些情况下,可以使用位运算来加速模运算,尤其是在模数为 2 的幂时。

8. 示例代码

以下是一个使用模运算的示例代码,计算斐波那契数列的第 n项模 m:

#include <iostream>
using namespace std;const int MOD = 1000000007;int fibonacci(int n) {if (n == 0) return 0;if (n == 1) return 1;int a = 0, b = 1, c;for (int i = 2; i <= n; ++i) {c = (a + b) % MOD;a = b;b = c;}return b;
}int main() {int n;cin >> n;cout << fibonacci(n) << endl;return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/34715.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

SpringBoot前后端不分离,前端如何解析后端返回html所携带的参数

有一个SpringBoot实现的前后端不分离项目&#xff0c;当前端跳转某个界面时&#xff0c;比如下面的菜单树按钮&#xff0c;后端在返回页面menuTree.html时&#xff0c;还携带了一个参数角色roleId&#xff0c;以便打开菜单树&#xff0c;还要根据这个角色查询对应的分配授权的菜…

操作系统八股文整理(一)

操作系统八股文整理 一、进程和线程的区别二、进程与线程的切换过程一、进程切换进程切换的步骤&#xff1a; 二、线程切换线程切换的步骤&#xff1a; 三、进程切换与线程切换的对比四、上下文切换的优化 三、系统调用一、系统调用的触发二、从用户空间切换到内核空间三、执行…

卷积神经网络(CNN)之 EfficientNet

在深度学习领域&#xff0c;模型的计算效率与性能之间的平衡一直是一个核心挑战。随着卷积神经网络&#xff08;CNN&#xff09;在图像分类、目标检测等任务中取得显著成果&#xff0c;模型的复杂度和计算需求也急剧增加。2019年&#xff0c;Google Research 提出的 EfficientN…

leetcode0031 下一个排列-medium

1 题目&#xff1a; 下一个排列 官方标定难度&#xff1a;中等 整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。 例如&#xff0c;arr [1,2,3] &#xff0c;以下这些都可以视作 arr 的排列&#xff1a;[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。 整数数组的 下一…

Suno的对手Luno:AI音乐开发「上传参考音频 - 方式二:通过URL的方式」 —— 「Luno Api系列|AI音乐API」第12篇

导读 今天来看下Luno Api的上传参考音频 - 方式一&#xff1a;通过二进制流的方式。 参考文件&#xff0c;主要是用于在创作的过程中&#xff0c;希望AI参考这个音乐的曲风和声音来进行创作&#xff0c; 这一节看看如何直接使用url的方式进行实现。 申请和使用 「已经有API…

【开源+代码解读】Search-R1:基于强化学习的检索增强大语言模型框架3小时即可打造个人AI-search

大语言模型(LLMs)在处理复杂推理和实时信息检索时面临两大挑战:知识局限性(无法获取最新外部知识)和检索灵活性不足(传统方法依赖固定检索流程)。现有方法如检索增强生成(RAG)和工具调用(Tool-Use)存在以下问题: RAG:单轮检索导致上下文不足,无法适应多轮交互场景…

Blender-MCP服务源码2-依赖分析

Blender-MCP服务源码2-依赖分析 有个大佬做了一个Blender-MCP源码&#xff0c;第一次提交代码是【2025年3月7号】今天是【2025年月15日】也就是刚过去一周的时间&#xff0c;所以想从0开始学习这个代码&#xff0c;了解一下大佬们的开发思路 1-核心知识点 from mcp.server.fas…

【孟德尔随机化】Leave-one-out analysis的异常点,判断

下面Leave-one-out analysis的结果&#xff0c;第一条线代表去掉rs174564的结果&#xff0c;一些文献把这种情况判断为异常点/离群点&#xff0c;我们接下来看看其他结果 散点图的结果&#xff0c;最旁边的就是rs174564&#xff0c;这个SNP的点 在看下RadialMR的结果&#xff0…

【计算机网络】2物理层

物理层任务:实现相邻节点之间比特(或)的传输 1.通信基础 1.1.基本概念 1.1.1.信源,信宿,信道,数据,信号 数据通信系统主要划分为信源、信道、信宿三部分。 信源:产生和发送数据的源头。 信宿:接收数据的终点。 信道:信号的传输介质。 数据和信号都有模拟或数字…

kubernetes|云原生|部署单master的kubernetes 1.25.5版本集群完全记录(使用contained 运行时)

一、 部署目标&#xff1a; kubernetes版本1.19&#xff0c;1.23的前后差异还是比较巨大的&#xff0c;到1.25版本&#xff0c;为了追求高性能&#xff0c;自然还是需要使用containerd&#xff0c;本文将主要讲述在centos7虚拟机下部署kubernetes 1.25.5集群&#xff0c;使用…

DeepSeek+Dify本地部署私有化知识库

1.Windows安装docker Windows安装Docker-CSDN博客 2.安装olloma https://ollama.com/ 安装完成&#xff0c;可以在桌面右下角看到olloma图标 3.安装deepseekR1模型 ollama官网&#xff08;deepseek-r1&#xff09;&#xff0c;找到deepseek模型 选择合适大小的模型&#xff…

[Linux][经验总结]Ubuntu6.11.0 docker更换镜像源(实操可用的正确方法)

一、前言 关于Ubuntu更换docker镜像源&#xff0c;网上有很多的教程&#xff0c;但在实操中发现&#xff0c;更换的源无法生效——原因是我的docker是在系统安装时&#xff0c;选择附加安装的package的方式安装的。 现将处理过程记录如下。 二、获取镜像源 在网上随便找个几…

NHANES指标推荐:BRI!

文章题目&#xff1a;Association of body roundness index with cardiovascular disease in patients with cardiometabolic syndrome: a cross-sectional study based on NHANES 2009-2018 DOI&#xff1a;10.3389/fendo.2025.1524352 中文标题&#xff1a;心脏代谢综合征患者…

3.水中看月

前言 这篇文章讲解套接字分配IP地址和端口号。这部分内容也相对有些枯燥&#xff0c;但并不难&#xff0c;而 且是学习后续那些有趣内容必备的基础知识&#xff08;计算机网络基础&#xff09;。 一、分配给套接字的IP地址与端口号 IP是InternetProtocol&#xff08;网络协议…

Linux驱动开发-①pinctrl 和 gpio 子系统②并发和竞争③内核定时器

Linux驱动开发-①pinctrl 和 gpio 子系统②并发和竞争③内核定时器 一&#xff0c;pinctrl 和 gpio 子系统1.pinctrl子系统2.GPIO子系统 二&#xff0c;并发和竞争1.原子操作2.自旋锁3.信号量4.互斥体 三&#xff0c;按键实验四&#xff0c;内核定时器1.关于定时器的有关概念1.…

奇安信二面

《网安面试指南》https://mp.weixin.qq.com/s/RIVYDmxI9g_TgGrpbdDKtA?token1860256701&langzh_CN 5000篇网安资料库https://mp.weixin.qq.com/s?__bizMzkwNjY1Mzc0Nw&mid2247486065&idx2&snb30ade8200e842743339d428f414475e&chksmc0e4732df793fa3bf39…

Python库安装报错解决思路以及机器学习环境配置详细方案

文章目录 概要第三方库gdalpymoltalibmahotasgraphviznltk-datalazypredictscikit-surprisenb_extensionspyqt5-toolsspacy、en_core_web_sm 机器学习GPU-torch安装torch_geometric安装ubuntu安装显卡驱动dlib安装torch-cluster、torch-scatter、torch-sparse和torch-geometric…

Power Apps 技术分享:连接SharePoint列表数据源

前言 在使用Power Apps的时候&#xff0c;使用列表作为数据源是非常方便和经济的&#xff0c;列表创建简单&#xff0c;SharePoint的存储也不像Dataverse需要按照容量付费。 正文 1.我们先在SharePoint中建一个列表&#xff0c;添加一些测试数据&#xff0c;如下图&#xff1a;…

【Linux】learning notes(4)cat、more、less、head、tail、vi、vim

文章目录 catmore 查看整个文件less 查看整个文件head 查看部分文件tail 查看部分文件vim / vi cat cat 命令在 Linux 和 Unix 系统中非常常用&#xff0c;它用于连接文件并打印到标准输出设备&#xff08;通常是屏幕&#xff09;。虽然 cat 的基本用法很简单&#xff0c;但它…

C++11函数包装器

目录 std::function 注意事项 包装静态成员函数 包装非静态成员函数 std::bind 用法 应用场景 std::function function是C11引入的类&#xff0c;可以用任何可调用对象作为参数&#xff0c;构造出一个新对象。 可调用对象有函数指针&#xff0c;仿函数&#xff0c;lamb…