裴蜀定理其实不是一种特殊的算法,他就是一个定理,来证明ax + by | gcd(x,y)
其实这个定理正确性显然,但是这个板子其实看不出来和这个定理有什么关系,这就很慌.
但是仔细一想,其实就是求出来这些数的gcd就行了,但是负数要变成正数.
题干:
题目描述 给出n个数(A1...An)现求一组整数序列(X1...Xn)使得S=A1X1+...AnXn>0,且S的值最小 输入输出格式 输入格式： 第一行给出数字N,代表有N个数 下面一行给出N个数 输出格式： S的最小值 输入输出样例 输入样例#1： 复制 2 4059 -1782 输出样例#1： 复制 99 说明 对于100%的数据，1≤n≤201 le n le 201≤n≤20，∣xi∣≤100000|x_i| le 100000∣xi∣≤100000
代码:
#include<iostream> #include<cstdio> #include<cmath> #include<ctime> #include<queue> #include<algorithm> #include<cstring> using namespace std; #define duke(i,a,n) for(int i = a;i <= n;i++) #define lv(i,a,n) for(int i = a;i >= n;i--) #define clean(a) memset(a,0,sizeof(a)) const int INF = 1 << 30; typedef long long ll; typedef double db; template <class T> void read(T &x) { char c; bool op = 0; while(c = getchar(), c < '0' || c > '9') if(c == '-') op = 1; x = c - '0'; while(c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; if(op) x = -x; } template <class T> void write(T x) { if(x < 0) putchar('-'), x = -x; if(x >= 10) write(x / 10); putchar('0' + x % 10); } int gcd(int x,int y)//y>x { int t; while(x > 0) { t = y % x; y = x; x = t; } return y; } ll k,ans; ll x[100010]; int main() { int n; read(n); duke(i,1,n) { read(x[i]); if(x[i] < 0) x[i] = -x[i]; } ans = gcd(x[1],x[2]); duke(i,3,n) { ans = gcd(ans,x[i]); } printf("%lld ",ans); return 0; }