[CSP-S模拟测试]:数列（数学）

题目传送门（内部题95）

输入格式

　　第一行三个整数$n,a,b$，第二行$n$个整数$x_1\sim x_n$表示数列。

输出格式

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

样例

样例输入：2 2 3
1 2

样例输出：

数据范围与提示

　　对于$10\%$的数据，$n,a,b,|x_i|\leqslant 1,000$。
　　对于$30\%$的数据，$n,a,b\leqslant 1,000$。
　　对于另外$10\%$的数据，$a=1$。
　　对于另外$10\%$的数据，$a=2,b=3$。
　　对于$100\%$的数据，$1\leqslant n\leqslant 10^5,1\leqslant a,b\leqslant 10^9,|x_i|\leqslant 10^9$。

题解

这道题是让我们解$xa+yb=x_i$，且要最小化$abs(x)+abs(y)$；那么，我们可以先用$exgcd$解出其中一组解$(x',y')$，那么解集就是$(x'+ka,y'-kb)$，那么$x$只会取最小的正值或最大的负值，分类讨论取最小值即可。

时间复杂度：$\Theta(n\log|x_i|)$。

期望得分：$100$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

using namespace std;

int n,a,b,x,y;

int s[100001];

long long ans;

int exgcd(int a,int b,int &x,int &y)

{

	int ret,tmp;

	if(!b){x=1;y=0;return a;}

	ret=exgcd(b,a%b,x,y);

	tmp=x;

	x=y;

	y=tmp-a/b*y;

	return ret;

}

int main()

{

	scanf("%d%d%d",&n,&a,&b);

	int gcd=__gcd(a,b);

	a/=gcd;b/=gcd;

	exgcd(a,b,x,y);

	for(int i=1;i<=n;i++)

	{

		scanf("%d",&s[i]);

		s[i]=abs(s[i]);

		if(s[i]%gcd){puts("-1");return 0;}

		s[i]/=gcd;

	}

	for(int i=1;i<=n;i++)

	{

		if(!s[i])continue;

		long long nowx=1LL*x*s[i];

		long long nowy=1LL*y*s[i];

		long long res=0x3f3f3f3f3f3f3f3f;

		long long dx=(nowx%b+b)%b;

		long long dy=nowy+(nowx-dx)/b*a;

		res=min(res,abs(dx)+abs(dy));

		dx-=b;dy+=a;

		res=min(res,abs(dx)+abs(dy));

		dy=(nowy%a+a)%a;

		dx=nowx+(nowy-dy)/a*b;

		res=min(res,abs(dx)+abs(dy));

		dx+=b;dy-=a;

		res=min(res,abs(dx)+abs(dy));

		ans+=res;

	}

	printf("%lld\n",ans);

	return 0;

}

rp++

巴特西