题解 | #小苯的优雅好序列#

F 小苯的优雅好序列

题目需要让 $a$ 数组中的每个连续子数组都是优雅的，容易看出其实我们只需要让所有长度为 $2$ 的连续子数组优雅就可以了。

那么接下来思考如何根据给定的 $a_i$ 和 $a_j$ 求出 $x$ 。

我们不妨设 $a_i \le a_j$ ，题目需要求出满足要求的 $(a_i x) | (a_j x)$ ，即存在一个正整数 $k$ 满足

a_j x = k (a_i x)

即

a_j - a_i = (k-1)(a_i x)

也就是 $(a_i x) | (a_j - a_i)$

所以我们只要枚举 $a_j - a_i$ 的因子即可。最后的 $x$ 其实就是用所有相邻两数之差 $a_i - a_{i-1}$ 的因子求出的 $x$ 的交集，所以我们先随便求一组差的解集，然后枚举所有的 $x$ ，验证即可。

由于一个数 $h$ 的因子数大概是 $\log$ 级别的，所以最后的时间复杂度为 $O(n \log a_i)$

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;

int a[N], n;

bool check(int x) {
	for (int i = 2; i <= n; i ++ ) {
		int val = abs(a[i] - a[i - 1]);
		if (val % (x + min(a[i], a[i - 1])) != 0) return false;
	}
	return true;
}

void solve() {
	int k;
	cin >> n >> k;
	for (int i = 1; i <= n; i ++ ) cin >> a[i];
	int pos = -1;
	for (int i = 2; i <= n; i ++ ) {
		if (a[i] == a[i - 1]) continue;
		if (pos == -1 || abs(a[i] - a[i - 1]) < abs(a[pos] - a[pos - 1]))
			pos = i;
	}
	if (pos == -1) {
		cout << k << ' ' << 1ll * (1 + k) * k / 2 << endl;
		return ;
	} 
	int val = abs(a[pos] - a[pos - 1]);
	vector<int> v;
	for (int i = 1; i * i <= val; i ++ ) {
		if (val % i) continue;
		int v1 = i - min(a[pos], a[pos - 1]);
		int v2 = val / i - min(a[pos], a[pos - 1]);
		if (v1 > 0 && v1 <= k) v.push_back(v1);
		if (v2 > 0 && v2 <= k) v.push_back(v2);
	}
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	int cnt = 0;
	LL sum = 0;
	for (int x : v) {
		// cout << x << ' ';
		if (check(x)) {
			cnt ++;
			sum += x;
		}
	}
	cout << cnt << ' ' << sum << endl;
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("1.in", "r", stdin);
	freopen("1.out", "w", stdout);
#endif
	int T; cin >> T;
	while (T -- ) solve();
	return 0;
}