洛谷P4549 裴蜀定理 / Min
2024-09-01 11:03:22
题目描述
给出n个数(A1...An)现求一组整数序列(X1...Xn)使得S=A1X1+...AnXn>0,且S的值最小
输入输出格式
输入格式:
第一行给出数字N,代表有N个数 下面一行给出N个数
输出格式:
S的最小值
输入输出样例
输入样例#1:
2
4059 -1782
输出样例#1:
99
题解
标题海星,直接给出正解……
裴蜀(贝祖)定理,就是关于\(x, y\)的不定方程\(ax + by = c\)有整数解的充要条件是\(\gcd(a, b)\mid c\)。
由此我们发现对于式子\(ax+by\)的值一定被\(\gcd(a, b)\)整除,于是就变成了\(k\times \gcd(a,b)\)。由于\(\gcd(a, b)\)已知,把它看成常数\(a\)即可。于是就把两项给合并了。
然后最终就变成了\(ax+by\)的最小非负值——那当然是\(\gcd(a, b)\)了。
就这样递推下去就行了,注意由于读入可能为负,读进来的时候取个绝对值即可(由于系数也反一下是无关的,所以结果是相同的)。
for(int i = 1, t; i <= n; ++i)
{
scanf("%d", &t);
if(t < 0)
t = -t;
ans = gcd(ans, t);
}
最新文章
- 混合使用TFVC和GIT配置库的优化方案
- delphi---控件使用
- dubbo源码分析2-reference bean发起服务方法调用
- Java:String和Date、Timestamp之间的转
- 55. Set Matrix Zeroes
- Bootstrap入门四:代码
- 轻松学习Ionic (三) 安装sass并在webstorm中为scss添加watcher
- Python闭包与函数对象
- linux内核源码阅读之facebook硬盘加速flashcache之四
- 关于ip通信学习感想
- JS的call与apply的用法
- Golang 优化之路-空结构[转]
- Get The Treasury HDU - 3642(扫描线求三维面积交。。体积交)
- imp高版本的dmp文件报错问题
- js便签笔记(12)——浏览TOM大叔博客的学习笔记 part2
- BootStrap 4正式版发布(原文翻译)
- linux大小写转换
- Bootstrap响应式布局
- [置顶]
 python3 django models保存filefiled字段统一目录、不修改文件名的方法
- 基于msm8909高通平台Android驱动开发之hello程序
热门文章
- [LeetCode] 684. Redundant Connection 冗余的连接
- [转]VS2017避免全部安装至C盘
- Failed to start LSB: Bring up/down networking 另外一个偏方
- SpringCloud Ribbon 负载均衡 通过服务器名无法连接的神坑一个
- python之lambda、filter、map、reduce的用法说明(基于python2)
- 微信小程序子组件样式不起作用的解决办法
- Centos 7.5 安装JDK
- 关于stm32f10x_conf.h文件
- html 四种定位含义
- Tomcat基础操作