当前位置: 首页 > news >正文

中国剩余定理 C++

题目

图源ACWING

解题思路

在这里插入图片描述
原链接:https://www.acwing.com/solution/content/3539/

大致步骤

  1. 将第2,3,4…n个方程不断与第一个方程合并,得到方程a1k1+a2k2=m2-m1;
  2. 用扩展欧几里得算法解出a1k1+a2k2=gcd(a1, a2)的结果,再将结果扩大(m2-m1)/d倍即可得到原方程解;
  3. k1通解=k1+a2/dk(k为整数),将k1代回x=a1k1+m1中,可得x=a1k1+a1a2/d*k+m1;
  4. 对比代回前后两方程可得:m1=m1+a1k1, a1=a1a2/d;
  5. 循环n-1次后所得m1就是结果;

代码实现

#include<iostream>
#include<algorithm>
#include<cmath>using namespace std;typedef long long LL;LL m1, a1;
LL a[50], m[50];
int n;LL exgcd(LL a, LL b, LL &x, LL &y)
{if(b == 0){x = 1, y = 0;return a;}LL x1, y1, t;t = exgcd(b, a % b, x1, y1);x = y1, y = x1 - a / b * y1;return t;
}void chinese_reminder_therome(LL a1, LL m1)
{for(int i = 2;i <= n;i ++ ){LL a2 = a[i];LL m2 = m[i];LL k1, k2;LL d = exgcd(a1, a2, k1, k2);if((m2 - m1) % d != 0)//只有(m2-m1)%d==0,才有整数解;{cout << -1;return ;}LL t = abs(a2 / d);k1 = k1 * (m2 - m1) / d;k1 = (k1 % t + t) % t;//找到k1的最小值,同时防止为k1为负数的写法m1 = m1 + a1 * k1;//先变m1再变a1,顺序不能变防止m1的变化受到a1的变化影响;a1 = a1 * a2 / d;}cout << m1;
}int main()
{cin >> n >> a1 >> m1;for(int i = 2;i <= n;i ++ ){scanf("%d%d", &a[i], &m[i]);}chinese_reminder_therome(a1, m1);return 0;
}

相关文章:

中国剩余定理 C++

题目 解题思路 原链接&#xff1a;https://www.acwing.com/solution/content/3539/ 大致步骤&#xff1a; 将第2,3,4…n个方程不断与第一个方程合并&#xff0c;得到方程a1k1a2k2m2-m1;用扩展欧几里得算法解出a1k1a2k2gcd(a1, a2)的结果&#xff0c;再将结果扩大(m2-m1)/d倍即…...

动态规划lc

先找到规律&#xff0c;然后找边界情况&#xff1b;部分特殊情况分类讨论 *递归 70.爬楼梯 简单 提示 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢&#xff1f; 示例 1&#xff1a; 输入&#xff1a…...

介绍xshell的使用技巧

使用技巧目录 1. 开启左键选中即复制&#xff0c;右键点击即粘贴2. 开启撰写功能3. 开启日志记录功能 1. 开启左键选中即复制&#xff0c;右键点击即粘贴 参考&#xff1a;https://blog.csdn.net/chirrupy_hamal/article/details/108619262 2. 开启撰写功能 使用场景&#x…...

揭秘语音识别巨头1:国内外顶尖技术服务商全解析01(万字长文)

一、学习导航 解密语音识别巨头&#xff1a;国内顶尖技术服务商全解析00&#xff1a;学习地图 解密语音识别巨头&#xff1a;国内顶尖技术服务商全解析01&#xff1a;微软语音&#xff0c;商业No.1 解密语音识别巨头&#xff1a;国内顶尖技术服务商全解析02&#xff1a;百度…...

JAVA使用SM2算法生成密钥对加密解密加签验签

简介 SM2是非对称加密算法&#xff0c;一提非对称加密算法&#xff0c;第一想到的是RSA&#xff0c;没错&#xff0c;这个就是替代RSA的。它是基于椭圆曲线密码的公钥密码算法标准&#xff0c;其秘钥长度256bit&#xff0c;包含数字签名、密钥交换和公钥加密&#xff0c;用于替…...

uniapp(vue)打包web项目页面刷新后报404解决方案

一、问题概述 uniapp是一款优秀的跨平台开发框架&#xff0c;它可以帮助开发者快速构建出适用于多端的应用程序。然而&#xff0c;在项目打包后&#xff0c;有可能发现页面在刷新时会出现404错误。这无疑给用户体验带来了极大的困扰&#xff0c;下面我们就来分析一下这个问题。…...

ansible学习之ansible-vault

相关文档参考:http://www.ansible.com.cn/docs/playbooks_vault.html#what-can-be-encrypted-with-vault ansible-vault 功能介绍 Ansible-Vault是一个用于加密和管理Ansible playbook中敏感数据的工具。通过创建、编辑、加密、解密、查看和重置密码&#xff0c;可以安全地存储…...

封装el-upload组件,用于上传图片和视频的组件

使用环境 vue3element plus 需要根据后端返回结构修改的函数&#xff1a;onPreview onRemove onSuccess 组件使用 基本使用 源代码&#xff1a; <script setup> import AutoUploadFile from /components/auto-upload-file/index.vue function change(urls){console.log…...

6.将扩散模型与其他生成模型的关联(2)

1.归一化流与扩散模型 自一化流(Normalizing Flow)是生成模型&#xff0c;通过将易于处理的分布进行变换以队对高维数据进行建模。归一化流可以将简单的概率分布转化为极其复杂的分布&#xff0c;并用于强化学习、变分推理等领域。 现有的归一化流是基于变量替换公式构…...

【C++】基于红黑树封装set和map

&#x1f680;个人主页&#xff1a;小羊 &#x1f680;所属专栏&#xff1a;C 很荣幸您能阅读我的文章&#xff0c;诚请评论指点&#xff0c;欢迎欢迎 ~ 目录 前言一、更高维度的泛型二、模版参数三、比较逻辑的重写四、迭代器4.1 const迭代器4.2 重载4.3 - -重载 五、完整代…...

24最新新手入门指南:Stable Diffusion!

前言 Stable Diffusion&#xff0c;一款新兴的开源AI绘画软件&#xff0c;正逐渐成为数字艺术家和爱好者的新宠。它的强大功能让用户能够轻松创造出令人印象深刻的数字艺术作品。 无论你是专业艺术家还是艺术新手&#xff0c;Stable Diffusion都为你提供了一个探索创造力的新…...

Java-基础

1. 导入模块不能纯粹的复制粘贴&#xff0c;要从new里导入&#xff0c;因为前者建立不了关联 2. 数组 String[] name{"张三","李四","王五"};int[] numsnew int[]{1,2,3};//二维String[][] names{{"张三","李四"},{"…...

二、后台管理系统布局菜单可拖动

前两天产品提出了一个需求,说后台管理系统的左边菜单的名称字数过多,遮挡了。希望能让客户能够看到全部的名称,给左侧菜单增加一个可拖动的功能,经过我的研究,这个功能最终也做出来了,先看效果,双击查看。 下面咱们进入实现步骤 第一步,找到文件。一般的项目中都存在l…...

socket和http区别

socket和http区别&#xff1a;1、主体不同&#xff1b;2、所处层次不同&#xff1b;3、连接状态不同&#xff1b;4、传输数据量不同&#xff1b;5、数据安全性不同&#xff1b;6、连接方式不同。其中&#xff0c;主体不同指的是socke是一个调用接口&#xff08;API&#xff09;…...

算法:974.和可以被K整除的子数组

题目 链接:leetcode链接 思路分析&#xff08;前缀和 同余定理&#xff09; 首先&#xff0c;我们要了解一下什么是同余定理 同余定理&#xff1a; 如果&#xff08;a - b&#xff09;/ p k …… 0 则 a % p b % p 证明我写在草稿纸上&#xff0c;如下图&#xff1a; 初…...

QD1-P8 HTML 格式化标签(font、pre、b、strong、i、u、del、s、sub、sup)

本节学习&#xff1a;HTML 格式化标签。 本节视频 www.bilibili.com/video/BV1n64y1U7oj?p8 ‍ 一、font 标签 用途&#xff1a;定义文本的字体大小、颜色和 face&#xff08;字体类型&#xff09;。 示例 <!DOCTYPE html> <html><head><meta cha…...

红米Turbo 3工程固件预览 修复底层 体验原生态系统 默认开启diag端口

红米Turbo 3机型代码:peridot 国外版本:POCO F6 用于以下型号的小米机型:24069RA21C, 24069PC21G, 24069PC21I。搭载1.5K OLED屏、骁龙8s处理器、5000mAh电池+90W快充、5000万像素主摄。 通过博文了解 1💝💝💝-----此机型工程固件的资源刷写注意事项 2💝💝�…...

sql的调优指南及高级sql技巧

SQL调优是优化数据库性能的重要手段&#xff0c;涉及编写高效的SQL查询、合理设计索引、优化数据库结构等。以下是一些SQL调优指南和高级技巧&#xff1a; SQL调优指南 选择合适的查询方式&#xff1a; **避免使用SELECT ***&#xff1a;仅选择所需的列&#xff0c;减少数据传…...

生成式专题的第一节课---GAN图像生成

一、GAN的起源与发展 1.GAN的起源 GAN &#xff08;生成式对抗网络&#xff09;诞生于 2014 年&#xff0c;由 Ian Goodfellow 提出&#xff0c;是用于生成数据的深度学习模型&#xff0c;创新点是对抗性训练&#xff0c;即生成器与判别器的竞争关系&#xff0c;为图像生成、…...

中科星图GVE(案例)——AI实现建筑用地变化前后对比情况

目录 简介 函数 gve.Services.AI.ConstructionLandChangeExtraction(image1,image2) 代码 结果 知识星球 机器学习 简介 AI可以通过分析卫星图像、航拍影像或其他地理信息数据&#xff0c;实现建筑用地变化前后对比。以下是一种可能的实现方法&#xff1a; 数据获取&am…...

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

谷歌浏览器插件

项目中有时候会用到插件 sync-cookie-extension1.0.0&#xff1a;开发环境同步测试 cookie 至 localhost&#xff0c;便于本地请求服务携带 cookie 参考地址&#xff1a;https://juejin.cn/post/7139354571712757767 里面有源码下载下来&#xff0c;加在到扩展即可使用FeHelp…...

C++:std::is_convertible

C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

6月9日&#xff0c;国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解&#xff0c;“超级…...

如何为服务器生成TLS证书

TLS&#xff08;Transport Layer Security&#xff09;证书是确保网络通信安全的重要手段&#xff0c;它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书&#xff0c;可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

Matlab | matlab常用命令总结

常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...

【VLNs篇】07:NavRL—在动态环境中学习安全飞行

项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战&#xff0c;克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...

搭建DNS域名解析服务器(正向解析资源文件)

正向解析资源文件 1&#xff09;准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2&#xff09;服务端安装软件&#xff1a;bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...