Cowlendar (USACO Silver 2024 January)

$N = 10^4$ ， $a_i$ 最大为 $4 \times 10^9$ ，需要找到所有大于 $a_i / 4$ 而且 $a_i \mod L$ 只有不超过3个值的L的和。

这个题基本上是个数学题，想得到抽屉原理就可以解，否则复杂度就过不去。

直观上，满足只出现 $3$ 种余数的 $L$ 很少，所以我们思考有没有数学方法，可以直接找出所有可能的 $L$ 。显然，如果 $a_i \equiv a_j \pmod{L}$ ，那么 $(a_i - a_j) \bmod L = 0$ ，也就是说这个时候 $L$ 一定是 $a_i - a_j$ 的约数。

那么，如何找到一对 $a_i$ 和 $a_j$ 使得它们模 $L$ 同余呢？我们可以对前 $4$ 个数 $a_1, a_2, a_3, a_4$ 应用鸽巢原理（抽屉原理）。因为只允许 $3$ 种不同的余数，所以根据鸽巢原理，前 $4$ 个数中必然有一对 $a_i, a_j$ 满足 $a_i \equiv a_j \pmod{L}$ 。

接下来，我们只需要枚举这些差值的所有约数 $L$ ，并验证每个 $L$ 是否满足所有 $a_i$ 取模后至多有 $3$ 种不同的余数即可。生成x的所有约数可以简单用枚举到 $\sqrt x$ 的方法，因为 $x$ 的范围是 $4\times 10^9$ ,开根之后复杂度可以接受。

Cowlendar (USACO Silver 2024 January)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n;
ll a[10005];
ll ans;
unordered_set<ll> checked;
ll maxL = 1e9;
 
// determine if L is a valid week length
void solve(ll L) {
    if (L > maxL) return;
    if (checked.count(L)) return;
    checked.insert(L);
    unordered_set<ll> remainders;
    if (L > 3) 
        for (int i = 0; i < n; i++) {
            remainders.insert(a[i] % L);
            if (remainders.size() > 3) return;
        }
    ans += L;
}
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%lld", &a[i]);
        maxL = min(maxL, a[i]/4);
    }
 
    // Deduplicate
    sort(a, a + n);
    n = unique(a, a + n) - a;
    if (n < 4) {   // 1 + 2 + ... + maxL
        ans = (maxL + 1) * maxL / 2;
        goto done;
    }
 
    // check all possible week lengths using pigeonhole principle
    for (int i = 0; i < 4; i++) {
        for (int j = i + 1; j < 4; j++) {
            ll diff = a[j] - a[i];
            // generate all divisors of diff
            vector<ll> divisors;
            for (ll d = 1; d * d <= diff; d++) {
                if (diff % d == 0) {
                    solve(d);
                    if (d * d != diff) solve(diff / d);
                }
            }
        }
    }
 
done:
    printf("%lld\n", ans);
    return 0;
}