1077 韩信点兵

这是一个中国剩余定理的问题。中国剩余定理是数论中的一个定理,它给出了一组同余方程的解的存在性和唯一性。在这个问题中,我们需要找到一个数,使得它对给定的每个质数取余的结果等于给定的余数。

以下是一个使用C++实现的解决方案:

#include <iostream>
#include <vector>
using namespace std;typedef long long ll;ll mul(ll a, ll b, ll mod) {ll res = 0;while (b) {if (b & 1) res = (res + a) % mod;a = (a + a) % mod;b >>= 1;}return res;
}ll qpow(ll a, ll b, ll mod) {ll res = 1;while (b) {if (b & 1) res = mul(res, a, mod);a = mul(a, a, mod);b >>= 1;}return res;
}ll exgcd(ll a, ll b, ll &x, ll &y) {if (!b) {x = 1;y = 0;return a;}ll d = exgcd(b, a % b, y, x);y -= a / b * x;return d;
}ll inv(ll a, ll mod) {ll x, y;exgcd(a, mod, x, y);return (x % mod + mod) % mod;
}int main() {vector<ll> A(8), a(8);for (int i = 0; i < 8; i++) cin >> A[i];for (int i = 0; i < 8; i++) cin >> a[i];ll M = 1;for (int i = 0; i < 8; i++) M *= A[i];ll res = 0;for (int i = 0; i < 8; i++) {ll Mi = M / A[i];res = (res + mul(mul(a[i], Mi, M), inv(Mi, A[i]), M)) % M;}cout << res << endl;return 0;
}

在这个代码中,我们首先定义了一些辅助函数,包括`mul`函数用于计算两个数的乘积对模取余的结果,`qpow`函数用于计算一个数的幂对模取余的结果,`exgcd`函数用于计算扩展欧几里得算法的结果,`inv`函数用于计算一个数的模逆元。然后,我们读入输入的质数和余数,计算出模数`M`,并初始化结果`res`为0。接着,我们遍历每一个质数和余数,计算出`Mi`,并更新`res`。最后,我们输出`res`,即满足条件的最小的一个数。

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

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

相关文章

【每日一练】Python遍历循环

1. 情节描述&#xff1a;上公交车(10个座位)&#xff0c;并且有座位就可以坐下 要求&#xff1a;输入公交卡当前的余额&#xff0c;只要超过2元&#xff0c;就可以上公交车&#xff1b;如果车上有空座位&#xff0c;才可以上。 seat 10 while seat > 0:money int(input(…

CentOS修复OpenSSH漏洞升级到openssh 9.7 RPM更新包

在做政府和学校单位网站时&#xff0c;经常需要服务器扫描检测&#xff0c;经常被OpenSSH Server远程代码执行漏洞&#xff08;CVE-2024-6387&#xff09;安全风险通告&#xff0c;出了报告需要升级OpenSSH。 使用yum update openssh是无法更新到最新的&#xff0c;因为系统里的…

JsonCpp:更简洁的序列化及反序列化

简介 jsoncpp 提供了一组简单易用的 API&#xff0c;使得在 C 程序中处理 JSON 数据变得更加方便和高效。 安装 linux环境下安装jsoncpp sudo apt-get update sudo apt-get install --reinstall libjsoncpp-dev建立软链接确保编译器找到头文件 #include <json/json.h>…

Vue原生写全选反选框

效果 场景&#xff1a;Vue全选框在头部&#xff0c;子框在v-for循环内部。 实现&#xff1a;点击全选框&#xff0c;所有子项选中&#xff0c;再次点击取消&#xff1b;子项全选中&#xff0c;全选框自动勾选&#xff0c;子项并未全选&#xff0c;全选框不勾选&#xff1b;已选…

LVM核心概念

1. LVM简介 LVM是逻辑盘卷管理&#xff08;Logical Volume Manager&#xff09;的简称&#xff0c;它是Linux环境下对磁盘分区进行管理的一种机制&#xff0c;LVM是建立在硬盘和分区之上的一个逻辑层&#xff0c;来提高磁盘分区管理的灵活性。 优点&#xff1a; 可以灵活分配…

大数据学习之Clickhouse

Clickhouse-23.2.1.2537 学习 一、Clickhouse概述 clickhouse 官网网址&#xff1a;https://clickhouse.com/ ClickHouse是一个用于联机分析(OLAP)的列式数据库管理系统(DBMS)。 OLTP(联机事务处理系统)例如mysql等关系型数据库&#xff0c;在对于存储小数据量的时候&#xff…

Langchain-Chatchat本地部署记录,三分钟学会!

1.前言&#xff1a; 最近AI爆发式的火&#xff0c;忆往昔尤记得16,17那会移动互联网是特别火热的&#xff0c;也造富了一批公司和个人&#xff0c;出来了很多精妙的app应用。现在轮到AI发力了&#xff0c;想想自己也应该参与到这场时代的浪潮之中&#xff0c;所以就找了开源的…

【TB作品】atmega16 计算器,ATMEGA16单片机,Proteus仿真

实验报告&#xff1a;基于ATmega16单片机的简易计算器设计 1. 实验背景 计算器是日常生活和工作中不可或缺的工具&#xff0c;通过按键输入即可实现基本的四则运算。通过本实验&#xff0c;我们将利用ATmega16单片机、矩阵键盘和LCD1602显示屏&#xff0c;设计并实现一个简易…

一招解决 | IP地址访问怎么实现https

没有域名的情况下&#xff0c;使用IP地址实现HTTPS访问是可以的&#xff0c;但相比使用域名会有些许限制&#xff0c;需要通过部署专用于IP地址的SSL/TLS证书来实现。 IP地址实现HTTPS访问的过程与使用域名类似&#xff0c;但有几个关键的区别。以下是使用IP地址实现HTTPS访问…

Win10 电脑屏幕保护怎么设置?学会了你也能轻松设置屏保

在 Windows 10 操作系统中&#xff0c;屏幕保护程序不仅能够为您的电脑增添个性化色彩&#xff0c;还能在长时间不操作电脑时保护屏幕免受烧屏影响。下面是一份详细指南&#xff0c;简鹿办公编辑教您如何通过 Windows 搜索框设置屏幕保护程序&#xff0c;并调整相关参数&#x…

uniapp——上传图片获取到file对象而非临时地址——基础积累

最近在看uniapp的代码&#xff0c;遇到一个需求&#xff0c;就是要实现上传图片的功能 uniapp 官网地址&#xff1a;https://uniapp.dcloud.net.cn/ 上传图片有对应的API&#xff1a; uni.chooseImage方法&#xff1a;https://uniapp.dcloud.net.cn/api/media/image.html#choo…

使用uniapp编写微信小程序

使用uniapp编写微信小程序 文章目录 使用uniapp编写微信小程序前言一、项目搭建1.1 创建项目方式1.1.1 HBuilderX工具创建1.1.2 命令行下载1.1.3 直接Gitee下载 1.2 项目文件解构1.2.1 安装依赖1.2.2 项目启动1.2.3 文件结构释义 1.2 引入uni-ui介绍 二、拓展2.1 uni-app使用uc…

“探索价值增长消费:让每一笔购物都成为增值之旅“

亲爱的顾客们&#xff0c;你们好&#xff01;今天&#xff0c;我将带你们探索一种革命性的消费哲学——价值增长消费&#xff0c;让每一次购物都成为一次增值之旅&#xff01; 在传统消费观念里&#xff0c;我们付出金钱换取商品或服务&#xff0c;随后这些便成为过去。但如今…

2024 年江西省研究生数学建模竞赛题目 B题投标中的竞争策略问题---完整文章分享(仅供学习)

问题&#xff1a; 招投标问题是企业运营过程中必须面对的基本问题之一。现有的招投标平台有国家级的&#xff0c;也有地方性的。在招投标过程中&#xff0c;企业需要全面了解招标公告中的相关信息&#xff0c;在遵守招投标各种规范和制度的基础上&#xff0c;选择有效的竞争策…

【AI绘画Stable Diffusion】教你制作 SD 光影文字,保姆级教程建议收藏!(附模型下载)

大家好&#xff0c;我是设计师阿威 最近光影文字又开始火起来了。今天讲讲怎么利用 Stable Diffusion 的 ControlNet 插件来制作光影图片。 1.下载光影模型组件 1.SD主模型&#xff1a;majicMIX realistic V6、xxmix9realistic_v26 2. ControlNet 的模型&#xff1a;Bright…

CV每日论文--2024.6.28

1、On Scaling Up 3D Gaussian Splatting Training 中文标题&#xff1a;扩展 3D 高斯泼溅训练 简介&#xff1a;3D高斯点描(3DGS)由于其卓越的视觉质量和渲染速度,越来越受欢迎用于3D重建。然而,3DGS的训练目前仅在单个GPU上进行,由于内存限制,它的处理高分辨率和大规模3D重建…

【海思Hi3403V100】多目拼接相机套板硬件规划方案

海思Hi3403V100 是专业超高清智能网络摄像头 SoC。该芯片最高支持四路 sensor 输入&#xff0c;支持最高 4K60fps 的 ISP 图像处理能力&#xff0c;支持 3F 、WDR、多级降噪、六轴防抖、硬件拼接、多光谱融合等多种传统图像增强和处理算法&#xff0c;支持通过AI 算法对输入图像…

【Qwen2部署实战】Qwen2初体验:用Transformers打造智能聊天机器人

系列篇章&#x1f4a5; No.文章1【Qwen部署实战】探索Qwen-7B-Chat&#xff1a;阿里云大型语言模型的对话实践2【Qwen2部署实战】Qwen2初体验&#xff1a;用Transformers打造智能聊天机器人3【Qwen2部署实战】探索Qwen2-7B&#xff1a;通过FastApi框架实现API的部署与调用4【Q…

windows USB 驱动开发-URB结构

通用串行总线 (USB) 客户端驱动程序无法直接与其设备通信。 相反&#xff0c;客户端驱动程序会创建请求并将其提交到 USB 驱动程序堆栈进行处理。 在每个请求中&#xff0c;客户端驱动程序提供一个可变长度的数据结构&#xff0c;称为 USB 请求块 (URB) &#xff0c;URB 结构描…