[CCPC陕西省赛2022 H题] Cute Rabbit

题目描述

有 \(n\) 只白色的兔子，把其中 \(m\) 只染成绿色。每只兔子上有一个数 \(a_i\) ，如果所有白色兔子上的数对所有绿色兔子上的数两两取余的值均相同，则该种染色方式合法，求能够使染色合法的最大的 \(m\) 。

输入格式

第一行有一个整数 \(n(2 \leq n \leq 10^5)\) ，表示兔子的数量。

第二行有 \(n\) 个整数 \(a_1, a_2, ..., a_n (1 \leq a_i \leq 10^6)\)。

输出格式

输出一行一个整数，表示问题的答案。

题解

首先考虑到的一种情况是把除了最小的数都涂成绿色，此时所有白数对绿数取余的答案都是其本身，显然合法。

考虑其他的情况。不难得出，所有绿色的数必须小于白色的数。因此，我们将所有数排序，之后枚举白数和绿数的分界线即可。此时，问题转化成了将前 \(i\) 个数染成绿色之后如何判断该染色方案是否合法。通过观察可以发现，染色合法的充分必要条件是 \(gcd(a_{i+1}, a_{i+2}, ..., a_n) \% lcm(a_1, a_2, ..., a_i) = 0\) 。因此，我们只需要预处理出前缀 \(lcm\) 和后缀 \(gcd\)即可 \(O(1)\) 的判断染色的合法性。

AC代码

//
// Created by wxy3265 on 2024/4/16.
//
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;

const int MAXN = 1e6 + 3;

int n;
int a[MAXN], l[MAXN], g[MAXN];

int gcd(int x, int y) {
    return y? gcd(y, x % y): x;
}
inline int lcm(int x, int y) {
    return x * y / gcd(x, y);
}

signed main() {
    int ans = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    sort(a + 1, a + 1 + n);
    for (int i = 2; i <= n; i++) {
        if (a[i] > a[1]) ans++;
    }
    if (ans == 0 || ans == n - 1) {
        cout << n - 1;
        return 0;
    }
    int tot = 1;
    for (int i = 1; i <= n; i++) {
        if (i == 1) l[i] = a[i];
        else l[i] = lcm(l[i - 1], a[i]);
        if (l[i] <= a[n]) tot++;
    }
    g[n - 1] = a[n] - a[n - 1];
    for (int i = n - 2; i > 0; i--) {
        g[i] = gcd(g[i + 1], a[i + 1] - a[i]);
    }
    g[n] = a[n];
    if (a[n] % l[n] == 0) ans = n - 1;
    for (int i = 1; i <= n - 1 && i <= tot - 1; i++) {
        if (g[i + 1] % l[i] == 0) {
            ans = max(ans, i);
        }
    }
    cout << ans << '\n';
    return 0;
}