array

　　　　　　by ysy

【题目描述】

    给定一个长度为n的数列，每次你可以进行以下操作之一：

(1)将一个数+a；

(2)将一个数-a；

(3)将一个数+b；

(4)将一个数-b；

你需要将所有数全部变为0，求最小操作数。

【输入数据】

       第一行三个整数n,a,b，第二行n个整数x₁~x_n表示数列。

【输出数据】

一行一个整数表示答案。无解输出-1。

【样例输入】

2 2 3

1 2

【样例输出】

 3

【数据范围】

对于10%的数据，n,a,b,|x_i|<=1000。

对于30%的数据，n,a,b<=1000。

对于另外10%的数据，a=1。

对于另外10%的数据，a=2，b=3。

对于100%的数据，1<=n<=10⁵，1<=a,b<=10⁹，|x_i|<=10⁹。

【题解思路】

很容易转化成数学模型：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
      
       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=0,f=1; char ch=getchar();    while(ch<'0'||ch>'9'){
    if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';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 = 0;    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