题目描述
有n只兔子,每个兔子上有一个数ai。要将所有兔子分为白色和绿色两堆,使所有白色兔子的数对绿色兔子取余结果相等。求绿色兔子的最大数量。
题解
考虑一种情况:把所有除了最小值的数都涂为绿色,此时显然满足条件。
对于一般情况:可以枚举白绿兔子的分割线x。
- 对于小于x,试将其全部涂为白色,计算x前缀的最小公倍数,记为lcm(x-1) 。
- 对于大于等于x,试将其全部涂为绿色,计算其后缀差分的最大公因数。记为gcd(x)。
此时可知满足涂色规则的充要条件即:gcd(x)%lcm(x-1)==0。
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+7;
int a[N],q[N],p[N];
int gcd(int a,int b){
return b!=0?gcd(b,a%b):a;
}
int lcm(int a,int b){
return a/gcd(a,b)*b;
}
signed main(){
bool flag=false;
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+n+1);
int minn=a[1],cnt=0,ans, tot = 2;
for(int i=1;i<=n;i++)if(a[i]==minn)cnt++;
q[1]=a[1];
if (cnt == 1 || cnt == n) {
cout << n - 1;
return 0;
}
ans = n - cnt;
for(int i=2;i<=n;i++) {
q[i]=lcm(q[i-1],a[i]);
if (q[i] <= a[n]) tot++;
}
for(int i=n-1;i>=1;i--)p[i]=gcd(p[i+1],a[i+1]-a[i]);
p[n]=a[n];
for(int i=1; i <= n - 1 && i <= tot - 1; i++){
if(p[i+1]%q[i]==0){
ans=max(ans, i);
flag=true;
}
}
cout << ans << "\n";
}
标签:竞赛,gcd,int,题解,兔子,程序设计,涂为
From: https://www.cnblogs.com/zwzww/p/18141174