array
by ysy
【题目描述】
给定一个长度为n的数列，每次你可以进行以下操作之一：
(1)将一个数+a；
(2)将一个数-a；
(3)将一个数+b；
(4)将一个数-b；
你需要将所有数全部变为0，求最小操作数。
【输入数据】
第一行三个整数n,a,b，第二行n个整数x1~xn表示数列。
【输出数据】
一行一个整数表示答案。无解输出-1。
【样例输入】
2 2 3
1 2
【样例输出】
3
【数据范围】
对于10%的数据，n,a,b,|xi|<=1000。
对于30%的数据，n,a,b<=1000。
对于另外10%的数据，a=1。
对于另外10%的数据，a=2，b=3。
对于100%的数据，1<=n<=105，1<=a,b<=109，|xi|<=109。
【题解思路】
很容易转化成数学模型：ax+by = c，使(|x|+|y|)min。
对于方程ax+by = c，我们可以用exgcd求出一组解。
当a,b互质时，保证ax+by = c有解。
设d = gcd(a,b).a/d*x+b/d*y = c/d;
此时可求出一组特解：x'，y'。
则ax+by = c的通解可以表示为：x = c/d * x' + k * b/d,y = c/d * y' - k * a/d;
然后如何使(|x|+|y|)min。考虑到对于上述通解，我们可以打表或意念理解，这是个单峰函数。
即存在唯一且确定值k，使得|c/d*x' + k*b/d|+|c/d*y' - k* a/d|最小，尽可能使绝对值接近零，那么对于这两个数使得x取得最小的正数或最大的负数（绝对值尽量接近0）。
时间复杂度 O(nlog|xi|)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define rep(k,i,j) for(int k = i;k <= j; ++k)
#define FOR(k,i,j) for(int k = i;k >= j; --k)
inline int read(){
int x=,f=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-'';ch=getchar();}
return x*f;
}
int n,a,b,k;
inline void exgcd(int a,int b,int m,ll &x,ll &y){
if(!b) x = m/a,y = ;
else {
exgcd(b,a%b,m,x,y);
swap(x,y);
y -= a/b*x;
}
}
inline int gcd(int a,int b){return b ? gcd(b,a%b) : a;}
ll x,y,p;
int main(){
freopen("array.in","r",stdin);
freopen("array.out","w",stdout);
n = read(),a = read(),b = read();
k = gcd(a,b);
a /= k,b /= k;
if(a<b) swap(a,b);
rep(i,,n){
int j = read();
if(j%k) printf("-1\n"),exit();
exgcd(a,b,j/k,x,y);
if(y<) {
x -= b*((-y)/a+);
y += a*((-y)/a+);
}
x += b*(y/a);
y -= a*(y/a);
p += min(abs(x)+abs(y),abs(x+b)+abs(y-a));
}
printf("%lld\n",p);
return ;
}
/*
2 2 3
1 2
*/