当前位置: 首页 > 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…...

HTML 语义化

目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案&#xff1a; 语义化标签&#xff1a; <header>&#xff1a;页头<nav>&#xff1a;导航<main>&#xff1a;主要内容<article>&#x…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试

作者&#xff1a;Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位&#xff1a;中南大学地球科学与信息物理学院论文标题&#xff1a;BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接&#xff1a;https://arxiv.…...

2024年赣州旅游投资集团社会招聘笔试真

2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术&#xff0c;它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton)&#xff1a;由层级结构的骨头组成&#xff0c;类似于人体骨骼蒙皮 (Mesh Skinning)&#xff1a;将模型网格顶点绑定到骨骼上&#xff0c;使骨骼移动…...

JavaScript基础-API 和 Web API

在学习JavaScript的过程中&#xff0c;理解API&#xff08;应用程序接口&#xff09;和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能&#xff0c;使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...

LabVIEW双光子成像系统技术

双光子成像技术的核心特性 双光子成像通过双低能量光子协同激发机制&#xff0c;展现出显著的技术优势&#xff1a; 深层组织穿透能力&#xff1a;适用于活体组织深度成像 高分辨率观测性能&#xff1a;满足微观结构的精细研究需求 低光毒性特点&#xff1a;减少对样本的损伤…...