比赛链接

2021-2022年度国际大学生程序设计竞赛第10届陕西省程序设计竞赛

H.Cute Rabbit

给出 \(n\) 个数，求最多选多少个数使得，所有未选的数对所有选的数的模数相等

解题思路

数论，gcd，lcm

• 时间复杂度：\(O(n)\)

代码

// Problem: Cute Rabbit
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/44727/H
// Memory Limit: 1048576 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include <bits/stdc++.h>
 
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
 
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
 
template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
 
template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=1e5+5,M=1e6+5;
int n,a[N],cnt[M];
int pre[N],suf[N];
int LCM(int x,int y)
{
	return x/__gcd(x,y)*y;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),cnt[a[i]]++;
    sort(a+1,a+1+n);
    if(cnt[a[1]]==n||cnt[a[1]]==1)
    {
    	printf("%d",n-1);
    	return 0;
    }
    int res=n-cnt[a[1]];
    pre[1]=a[1];
    int tot=2;
    while(tot<=n&&LCM(pre[tot-1],a[tot])<=a[n])pre[tot]=LCM(pre[tot-1],a[tot]),tot++;
    suf[n-1]=a[n]-a[n-1];
    for(int i=n-2;i>=1;i--)suf[i]=__gcd(suf[i+1],a[i+1]-a[i]);
    for(int i=2;i<=tot&&i<=n;i++)
    	if(suf[i]%pre[i-1]==0)
    		res=max(res,i-1);
    printf("%d",res);
    return 0;
}