Min(BZOJ 1441)
2024-08-30 13:02:54
题目描述
给出n个数(A1...An)现求一组整数序列(X1...Xn)使得S=A1*X1+...An*Xn>0,且S的值最小
输入
第一行给出数字N,代表有N个数 下面一行给出N个数
输出
S的最小值
样例输入
2
4059 -1782
4059 -1782
样例输出
99
/*
(裴蜀定理:ax+by的最小正整数值为gcd(a,b))
首先,将题意简化,设n=2,那么,就是求a1*x1+a2*x2=S的最小正整数值。
根据扩展欧几里得可以知道当gcd(a1,a2)|S时,gcd为最小正整数解。
拓展题意,就是a1、a2 ……an的gcd值。
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
using namespace std;
int gcd(int a,int b)
{
if(!b)return a;
return gcd(b,a%b);
}
int main()
{
int n,ans;
scanf("%d%d",&n,&ans);
for(int i=;i<=n;i++)
{
int x;
scanf("%d",&x);
ans=gcd(ans,x);
}
printf("%d",abs(ans));
return ;
}
最新文章
- TP中的session和cookie
- 聊Javascript中的AOP编程
- MMORPG大型游戏设计与开发(客户端架构 part15 of vegine)
- javascript坐标:event.x、event.clientX、event.offsetX、event.screenX 用法
- html5游戏引擎phaser官方示例学习
- SGU 106 The equation 扩展欧几里得好题
- jsp内置对象和el表达式
- macro names must be identifiers
- 编译驱动时出现";Cannot open file trace.h";错误
- mvc 生成输出url
- ASIFormDataRequest 上传图片
- 搭建SSH
- 分享一个markdownpad2的授权key
- 201521123035《Java程序设计》第八周学习总结
- vue 学习中 版本、问题集锦
- js 对象属性遍历
- MySQL:(二)
- [转] 多核CPU 查看进程分配的CPU具体核id
- WPF中,输入完密码回车提交 ,回车触发按钮点击事件
- gentoo 建立本地软件库并安装软件 Custom repository
热门文章
- cookie安全
- jni ndk 入门
- blog.yiz96.com
- vue for循环中常见问题 之 求和(合计)
- js获得本季度的开始日期 结束日期
- Respond.js-----20150415
- 条款37:绝不重新定义继承而来的缺省参数值(Never redefine a function&#39;s inherited default parameter value)
- Linux文件权限与文件夹权限实践
- leetcode-3-basic-divide and conquer
- (转)git clone: error: RPC failed; result=18, HTTP code = 200 解决办法