自闭了……考场上exgcd打错然后对着屏幕自闭了一个小时不知道它为什么解得不对
开始恶补:
对于方程 \(a*x+b*y=c\) ,就等价于 \(a*x \equiv c\pmod{b}\)
首先它有解的条件是 \(c \mid gcd(a, b)\)
然后exgcd可以用来求一组 \(x, y\) 满足 \(a*x+b*y=gcd(a, b)\)
所以把解出来的 \(x, y\) 除gcd再乘上c就可以得到一组解
然后在 \(gcd(a, b)=1\) 的条件下解集为 \((a+k*b, b+k*a)\)
特别注意这里的 \(gcd(a, b)=1\) ,我被这玩意坑了半天
对应到这道题里,要求的就是 \(min\{abs(x)+abs(y)\}\)
按 \(x, y\) 的正负分情况讨论,让 \(abs(x-k*b)+abs(y+k*a)\) 尽量变小
具体来说,当 \(x \geqslant 0, y \geqslant 0\) 时,考虑 \(a, b\) 的大小关系
可以发现要让大的那个系数为负,比较 \(x\) 是最小的那个正数和是最大的那个负数的大小
其它情况类似
Code:
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define N 100010
#define ll long long
//#define int long long
char buf[1<<21], *p1=buf, *p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<21, stdin)), p1==p2?EOF:*p1++)
inline int read() {
int ans=0, f=1; char c=getchar();
while (!isdigit(c)) {if (c=='-') f=-f; c=getchar();}
while (isdigit(c)) {ans=(ans<<3)+(ans<<1)+(c^48); c=getchar();}
return ans*f;
}
int n; ll a, b;
ll x[N], ans;
ll exgcd(ll a, ll b, ll& x, ll& y) {
if (!b) {x=1, y=0; return a;}
ll g=exgcd(b, a%b, y, x);
y-=(a/b)*x;
return g;
}
signed main()
{
n=read(); a=read(); b=read();
if (a>b) swap(a, b);
ll x1, y1;
ll g=exgcd(a, b, x1, y1);
a/=g, b/=g;
//cout<<"xy: "<<x1<<' '<<y1<<endl;
for (int i=1; i<=n; ++i) x[i]=read();
for (int i=1; i<=n; ++i) {
//cout<<i<<": "<<endl;
if (x[i]%g) {puts("-1"); return 0;}
ll x2=x[i]*x1/g, y2=x[i]*y1/g, k=llabs(x2/b);
//cout<<"xyk: "<<x2<<' '<<y2<<' '<<k<<endl;
if (x2>=0 && y2>=0) ans+=min(llabs(x2-k*b)+llabs(y2+k*a), llabs(x2-(k+1)*b)+llabs(y2+(k+1)*a));
else if (x2<=0 && y2>=0) ans+=min(llabs(x2+k*b)+llabs(y2-k*a), llabs(x2+(k+1)*b)+llabs(y2-(k+1)*a));
else if (x2>=0 && y2<=0) ans+=min(llabs(x2-k*b)+llabs(y2+k*a), llabs(x2-(k+1)*b)+llabs(y2+(k+1)*a));
else puts("error");
}
printf("%lld\n", ans);
return 0;
}