题目描述

给出n个数(A1...An)现求一组整数序列(X1...Xn)使得S=A1*X1+...An*Xn>0,且S的值最小

输入

第一行给出数字N,代表有N个数 下面一行给出N个数

输出

S的最小值

样例输入

2
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 ;
}

最新文章

  1. TP中的session和cookie
  2. 聊Javascript中的AOP编程
  3. MMORPG大型游戏设计与开发(客户端架构 part15 of vegine)
  4. javascript坐标:event.x、event.clientX、event.offsetX、event.screenX 用法
  5. html5游戏引擎phaser官方示例学习
  6. SGU 106 The equation 扩展欧几里得好题
  7. jsp内置对象和el表达式
  8. macro names must be identifiers
  9. 编译驱动时出现&quot;Cannot open file trace.h&quot;错误
  10. mvc 生成输出url
  11. ASIFormDataRequest 上传图片
  12. 搭建SSH
  13. 分享一个markdownpad2的授权key
  14. 201521123035《Java程序设计》第八周学习总结
  15. vue 学习中 版本、问题集锦
  16. js 对象属性遍历
  17. MySQL:(二)
  18. [转] 多核CPU 查看进程分配的CPU具体核id
  19. WPF中,输入完密码回车提交 ,回车触发按钮点击事件
  20. gentoo 建立本地软件库并安装软件 Custom repository

热门文章

  1. cookie安全
  2. jni ndk 入门
  3. blog.yiz96.com
  4. vue for循环中常见问题 之 求和(合计)
  5. js获得本季度的开始日期 结束日期
  6. Respond.js-----20150415
  7. 条款37:绝不重新定义继承而来的缺省参数值(Never redefine a function&#39;s inherited default parameter value)
  8. Linux文件权限与文件夹权限实践
  9. leetcode-3-basic-divide and conquer
  10. (转)git clone: error: RPC failed; result=18, HTTP code = 200 解决办法