中国剩余定理——AcWing 204. 表达整数的奇怪方式

2024-06-19 06:36

本文主要是介绍中国剩余定理——AcWing 204. 表达整数的奇怪方式,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

中国剩余定理

定义

中国剩余定理最早出自我国古代的《孙子算经》,是数论中的一个重要定理。它描述了这样一种情况:在模运算下,对于一组线性同余方程组,存在唯一解的条件和求解方法。

运用情况

常用于在一些涉及到按不同模的余数条件下求解问题。比如在密码学、计算数论、计算机科学等领域中,当需要处理多个模条件相关的计算时,常常会用到中国剩余定理。

注意事项

  • 要求各个模之间互质,否则定理不直接适用,可能需要进行一些转化处理。
  • 在计算过程中要保证计算的准确性,尤其是涉及到较大数的运算时。

解题思路

AcWing 204. 表达整数的奇怪方式   

题目描述

AcWing 204. 表达整数的奇怪方式 - AcWing

运行代码

#include <iostream>
#define int long long
using namespace std;
int n;
int exgcd(int a, int b, int &x, int  &y)
{if(!b){x = 1, y = 0;return a;}int d = exgcd(b, a % b, y, x);y -= a / b * x;return d;
}
signed main()
{bool st = true;cin >> n;int a1, m1;cin >> a1 >> m1;for(int i = 2; i <= n; i ++ ){int a2, m2, k01, k02, d;cin >> a2 >> m2;d = exgcd(a1, a2, k01, k02);if((m2 - m1) % d) {st = false;break;}k01 = k01 * (m2 - m1) / d;k01 = (k01 % (a2 / d) + (a2 / d)) % (a2 / d);m1 += a1 * k01;a1 = a1 / d * a2;}if(st) cout << (m1 % a1 + a1) % a1 << endl;else cout << -1 << endl;return 0;
} 

代码思路

  1. 类型定义与变量初始化

    • 使用 #define int long long 将整型变量默认定义为长整型,以处理大数。
    • 定义全局变量 n 表示同余方程的数量。
  2. 扩展欧几里得算法(exgcd): 实现了扩展欧几里得算法,用于求解形如 ax + by = gcd(a, b)ax+by=gcd(a,b) 的方程。返回值 d 是 aa 和 bb 的最大公约数(GCD),同时通过引用参数 xy 返回系数。这个函数是解决CRT的关键,用于寻找模数之间的关系。

  3. 主函数(main)

    • 首先读入同余方程的数量 n
    • 初始化第一个方程的系数 a1 和模数 m1
    • 对于每个后续的方程(从第二个到第 n 个),执行以下操作:
      • 读取当前方程的系数 a2 和模数 m2
      • 使用 exgcd 函数计算 a1 和 a2 的最大公约数 d,以及对应的系数 k01k02
      • 检查是否存在解:如果 (m2 - m1)(m2−m1) 不能被 d 整除,则说明无解,标记 st 为 false 并跳出循环。
      • 如果有解,根据中国剩余定理调整 m1 和 a1,使得它们分别表示合并后的同余方程的临时解和新模数。
    • 最后,根据 st 的值输出结果:如果为 true,则输出满足所有同余条件的最小非负整数解;否则,输出 -1 表示无解。

改进思路

  1. 使用更明确的变量名:虽然简短的变量名让代码紧凑,但更具有描述性的名称可以提高代码的可读性。例如,可以将 a1, a2, m1, m2 等变量名改为 current_coefficient, next_coefficient, current_modulus, next_modulus 等。

  2. 避免全局变量:全局变量 n 可能导致代码的维护和理解难度增加,尤其是在大型项目中。可以考虑将其作为函数参数传递。

  3. 优化解的计算和输出

    • 直接计算最终解而不仅仅是累积操作。在循环结束后,可以计算最终的 x(即满足所有同余方程的解)并直接取模,避免最后对 a1 进行额外的模运算。
    • 输出解时,使用 % 运算符可能两次取模,实际上 (m1 % a1 + a1) % a1 可以简化为 (m1 % a1),因为当 m1 < 0 时,(m1 + a1) % a1 已经保证结果非负。
  4. 增加错误处理和注释:对于输入验证(如检查模数是否两两互质、是否为正整数等)添加更多的错误处理逻辑,并在关键步骤添加注释,帮助读者理解算法逻辑。

  5. 模块化设计:将中国剩余定理的求解过程封装成一个独立的函数,而不是全部放在 main 函数中,这样可以提高代码的复用性和可测试性。

  6. 考虑大数运算库:如果要处理非常大的数字,可以考虑使用专门的大数运算库(如 GMP 库),这会比直接使用 C++ 内置数据类型更高效且支持更大的数值范围。

  7. 优化扩展欧几里得算法的实现:虽然现有实现是标准的,但在某些特定情况下,可以通过一些小技巧进一步优化,比如利用幂次计算减少递归深度,或是迭代法替代递归以节省栈空间。

这篇关于中国剩余定理——AcWing 204. 表达整数的奇怪方式的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1074276

相关文章

JAVA封装多线程实现的方式及原理

《JAVA封装多线程实现的方式及原理》:本文主要介绍Java中封装多线程的原理和常见方式,通过封装可以简化多线程的使用,提高安全性,并增强代码的可维护性和可扩展性,需要的朋友可以参考下... 目录前言一、封装的目标二、常见的封装方式及原理总结前言在 Java 中,封装多线程的原理主要围绕着将多线程相关的操

Golang中拼接字符串的6种方式性能对比

《Golang中拼接字符串的6种方式性能对比》golang的string类型是不可修改的,对于拼接字符串来说,本质上还是创建一个新的对象将数据放进去,主要有6种拼接方式,下面小编就来为大家详细讲讲吧... 目录拼接方式介绍性能对比测试代码测试结果源码分析golang的string类型是不可修改的,对于拼接字

Linux下修改hostname的三种实现方式

《Linux下修改hostname的三种实现方式》:本文主要介绍Linux下修改hostname的三种实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux下修改ho编程stname三种方式方法1:修改配置文件方法2:hFvEWEostnamectl命

SpringBoot接收JSON类型的参数方式

《SpringBoot接收JSON类型的参数方式》:本文主要介绍SpringBoot接收JSON类型的参数方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、jsON二、代码准备三、Apifox操作总结一、JSON在学习前端技术时,我们有讲到过JSON,而在

Spring Security注解方式权限控制过程

《SpringSecurity注解方式权限控制过程》:本文主要介绍SpringSecurity注解方式权限控制过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、摘要二、实现步骤2.1 在配置类中添加权限注解的支持2.2 创建Controller类2.3 Us

SpringBoot操作MaxComputer方式(保姆级教程)

《SpringBoot操作MaxComputer方式(保姆级教程)》:本文主要介绍SpringBoot操作MaxComputer方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的... 目录引言uqNqjoe一、引入依赖二、配置文件 application.properties(信息用自己

Java中数组转换为列表的两种实现方式(超简单)

《Java中数组转换为列表的两种实现方式(超简单)》本文介绍了在Java中将数组转换为列表的两种常见方法使用Arrays.asList和Java8的StreamAPI,Arrays.asList方法简... 目录1. 使用Java Collections框架(Arrays.asList)1.1 示例代码1.

java两个List的交集,并集方式

《java两个List的交集,并集方式》文章主要介绍了Java中两个List的交集和并集的处理方法,推荐使用Apache的CollectionUtils工具类,因为它简单且不会改变原有集合,同时,文章... 目录Java两个List的交集,并集方法一方法二方法三总结java两个List的交集,并集方法一

Python中如何控制小数点精度与对齐方式

《Python中如何控制小数点精度与对齐方式》在Python编程中,数据输出格式化是一个常见的需求,尤其是在涉及到小数点精度和对齐方式时,下面小编就来为大家介绍一下如何在Python中实现这些功能吧... 目录一、控制小数点精度1. 使用 round() 函数2. 使用字符串格式化二、控制对齐方式1. 使用

Nginx配置系统服务&设置环境变量方式

《Nginx配置系统服务&设置环境变量方式》本文介绍了如何将Nginx配置为系统服务并设置环境变量,以便更方便地对Nginx进行操作,通过配置系统服务,可以使用系统命令来启动、停止或重新加载Nginx... 目录1.Nginx操作问题2.配置系统服android务3.设置环境变量总结1.Nginx操作问题