欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

洛谷P4549 裴蜀定理

程序员文章站 2022-05-09 13:01:26
...
这个字这么难打的么??

题目描述

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

输入输出格式

输入格式:
第一行给出数字N,代表有N个数 下面一行给出N个数

输出格式:
S的最小值

输入输出样例

输入样例#1:
2
4059 -1782
输出样例#1:
99
说明

对于100%的数据,1 \le n \le 201≤n≤20,|x_i| \le 100000∣x
i
​ ∣≤100000


关于L_Y_T的懒癌,emmmmmm


#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <math.h>

using namespace std ;
int gcd(int a ,int b) ;
int n ,x;
int read() {
	int x = 0 ; int f = 1 ;char s = getchar() ;
	while(s > '9' || s < '0') {if(s=='-')f=-1;s=getchar();}
	while(s<='9'&&s>='0') {x=x*10+(s-'0');s=getchar();}
	return x*f ;
}
int main() {
	n = read() ;int ans=0;
	for(int i = 1 ; i <= n ; i ++){
		x = read() ;
		ans = gcd(ans,x) ;
	}
	cout << abs(ans) << endl ;
	return 0 ;
}
int gcd(int a,int b) {
	return b==0? a:gcd(b,a%b) ; 
}

真的不想多大注释emmmm

相关标签: 数论