洛谷P10136 暨 USACOJan2024S T3 题解

题意简述

原题已经很简了，没有什么简述的必要了。

思维路径

请注意本题解可以保证正确性但不保证如果有极端的 Hack 数据能够通过。

拿到这道题上来的暴力想必是很容易的，即枚举每个 \(L\) 判断是否合法。

接着我们就考虑优化，减少需要枚举的 \(L\) 的量。题目中要求余数最多有 \(3\) 种，而余数相同对的数相减所得的数的约数才有可能作为 \(L\)。

我们对 \(a\) 数组进行排序，则由于抽屉原理，最小的四个数一定有两个是同余的，枚举他们的差的约束，如果算过就直接跳过，否则就暴力算是否满足。如果存在一个数是满足上述条件的，那么它的约数就一定也满足，可以直接标记。

在目前的数据下这个做法是可以通过的，但是要是这个差很大就 emmmm。

AC 代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=100009;
ll n,a[N],nn,ans,x;
map<ll,ll> ok,vst;

void input(){
	cin>>n;
	for(ll i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+n+1);
	for(ll i=1,j=1;i<=n;i++){
		if(a[i]==a[i-1]) continue;
		a[j]=a[i]; nn=j; j++;
//		cout<<a[j];
	}
	n=nn;
}

void cal(ll u){
	vst.clear();
	ll cnt=0;
	for(ll i=1;i<=n;i++){
		if(!vst[a[i]%u]) cnt++;
		vst[a[i]%u]=1;
	}
	if(cnt<=3){
		for(ll i=1;i*i<=u;i++){
			if(u%i) continue;
			if(!ok[i]) ans+=i;
			ok[i]=1;
			if(!ok[u/i]) ans+=u/i;
			ok[u/i]=1;
		}
	}
}

void solve(){
	if(n<=3){
		cout<<(1+a[1]/4)*(a[1]/4)/2;
		return;
	}
	ok[1]=ok[2]=ok[3]=1; ans=6;
	x=a[2]-a[1];
	for(ll i=1;i*i<=x;i++){
		if(x%i==0){
			if(x/i<=a[i]/4&&(!ok[x/i])) cal(x/i);
			if(i<=a[i]/4&&(!ok[i])) cal(i);
		}
	}
	x=a[3]-a[1];
	for(ll i=1;i*i<=x;i++){
		if(x%i==0){
			if(x/i<=a[i]/4&&(!ok[x/i])) cal(x/i);
			if(i<=a[i]/4&&(!ok[i])) cal(i);
		}
	}
	x=a[4]-a[1];
	for(ll i=1;i*i<=x;i++){
		if(x%i==0){
			if(x/i<=a[i]/4&&(!ok[x/i])) cal(x/i);
			if(i<=a[i]/4&&(!ok[i])) cal(i);
		}
	}
	x=a[3]-a[2];
	for(ll i=1;i*i<=x;i++){
		if(x%i==0){
			if(x/i<=a[i]/4&&(!ok[x/i])) cal(x/i);
			if(i<=a[i]/4&&(!ok[i])) cal(i);
		}
	}
	x=a[4]-a[2];
	for(ll i=1;i*i<=x;i++){
		if(x%i==0){
			if(x/i<=a[i]/4&&(!ok[x/i])) cal(x/i);
			if(i<=a[i]/4&&(!ok[i])) cal(i);
		}
	}
	x=a[4]-a[3];
	for(ll i=1;i*i<=x;i++){
		if(x%i==0){
			if(x/i<=a[i]/4&&(!ok[x/i])) cal(x/i);
			if(i<=a[i]/4&&(!ok[i])) cal(i);
		}
	}
	cout<<ans;
}

int main(){
	input();
	solve();
	return 0;
}