日常训练2025-1-17

rating：1500

https://codeforces.com/problemset/problem/2007/C

思路（裴蜀定理）

碰到要么加a 要么加 b 的题一定要想到裴蜀定理， ax + by = gcd(a, b)。即每个数可以加减k*gcd(a, b)。

所以我们可以把每个数都调整到只相差小于gcd(a, b)的范围内。这样会贡献一次答案。

然后每个数都可以做一次最大值和最小值，枚举一遍再求答案即可。

代码

#include <bits/stdc++.h>

typedef std::pair<long long, long long> pll;
typedef std::pair<int, int> pii;
#define INF 0x3f3f3f3f
#define MOD 998244353
using i64 = long long;
const int N = 1e5+5;

void solve(){
	int n, a, b;
	std::cin >> n >> a >> b;

	int d = std::gcd(a, b);

	std::vector<int> v(n);
	for (int i = 0; i < n; i++){
		std::cin >> v[i];
		v[i] %= d;
	}
	std::sort(v.begin(), v.end());

	int ans = v[n-1] - v[0];
	for (int i = 1; i < n; i++){
		ans = std::min(ans, v[i-1]+d-v[i]);
	}

	std::cout << ans << '\n';
}

signed main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout<<std::setiosflags(std::ios::fixed)<<std::setprecision(2);
	int t = 1, i;
	std::cin >> t;
	for (i = 0; i < t; i++){
		solve();
	}
	return 0;
}