奶牛日历(Cowlendar) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <algorithm>
#include <iostream>
#include <set>
#include <unordered_set>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());

    long long maxL = a[0] / 4;
    if ((int)a.size() <= 3) {
        cout << maxL * (maxL + 1) / 2 << "\n";
        return 0;
    }

    set<long long> cands;
    for (int i = 0; i < 4; ++i) {
        for (int j = i + 1; j < 4; ++j) {
            long long diff = a[j] - a[i];
            for (long long d = 1; d * d <= diff; ++d) {
                if (diff % d == 0) {
                    if (d <= maxL) cands.insert(d);
                    if (diff / d <= maxL) cands.insert(diff / d);
                }
            }
        }
    }

    long long ans = 0;
    for (long long L : cands) {
        long long r0 = -1, r1 = -1, r2 = -1;
        bool ok = true;
        for (long long x : a) {
            long long r = x % L;
            if (r == r0 || r == r1 || r == r2) continue;
            if (r0 == -1) r0 = r;
            else if (r1 == -1) r1 = r;
            else if (r2 == -1) r2 = r;
            else { ok = false; break; }
        }
        if (ok) ans += L;
    }
    cout << ans << "\n";
    return 0;
}