题解：P10136 [USACO24JAN] Cowlendar S

早上打模拟赛败在你上面，下午改题改了半天，晚上又在 Ad-hoc 题单里相见，那我就写篇题解纪念。

题目链接

思路

一般这种取模题三个套路：

1. 取模余数相同 \(\rightarrow\) 作差之后值为模数的倍数；
2. 取模后减小范围或判断整除；
3. \(a \leq b\) 时，\(a \bmod b \leq \frac{a}{2}\)。

这个题是想让我们找出一定范围内的数字 \(k\) 对整个序列取模后的所有余数不超过 3 个，明显是用第一条。

然后我们就可以先把这些数字（前提是同余）两两作差，判断所有差值的因子是否合法即可。时间复杂度 \(O(n^3 \sqrt{V})\)，\(V\) 是值域。

但是 \(n \leq 10^4\) 且 \(1 \leq a_i \leq 4 \times 10^9\)，我们上面的做法还是太暴力了，我们不可能在值域上动手脚，只能考虑怎么枚举更少的数找出同余的数对。

注意到不同余数上限只有 3，同时 \(n\) 基本上大于这个数，于是我们想到了鸽巢原理。

不知道鸽巢原理是啥也没关系，我们这么去理解：给出一些形状大小都相同的彩球，我们知道彩球的颜色数小于彩球的数量，把它们都放到一个箱子里，问题要从中至少摸几个球才能保证摸出两个颜色相同的球。这很简单，只要次数超过颜色数即可。

运用到这个题上，在余数只有三个的前提下，我们就能想到随便拿出 4 个数字，就一定能保证它们模 \(k\) 后一定有两个数字同余，然后用上面的方法就可以求出答案。

但是注意我们上面所说的都是建立在所有数字均不相等的情况，所以我们要先去重再计算。

你说数列小于 3 怎么办？数字个数都没有 3 个怎么模出来 4 个余数，特判一下就行。

时间复杂度：\(O(n \sqrt{V})\)，\(V\) 是值域，可以通过本题。

代码

枚举因子这里应该还能优化，但是我懒就这样吧。

#include <bits/stdc++.h>
#define int long long
using namespace std;const int MN = 1e4 + 3;
int n, a[MN], m, ans;
set<int> st;bool check(int x) {set<int> ts;for (int i = 1; i <= n; i++) {ts.insert(a[i] % x);if (ts.size() > 3) return false;}return true;
}signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];sort(a + 1, a + n + 1);n = unique(a + 1, a + n + 1) - a - 1;m = a[1] / 4;if (n <= 3) return cout << (1 + m) * m / 2, 0;for (int i = 1; i <= 4; i++) {for (int j = i + 1; j <= 4; j++) {int cur = abs(a[j] - a[i]);for (int x = 1; x * x <= cur && x <= m; x++) {if (cur % x) continue;if (check(x)) st.insert(x);int tx = cur / x;if (tx <= m && check(tx)) st.insert(tx);}}}for (int x : st) ans += x;cout << ans;return 0;
}