1月USACO計(jì)算機(jī)競(jìng)賽'銀牌'解題分析（完整版可領(lǐng)?。?/h1>

發(fā)布時(shí)間：2024-02-02 09:34:32

編輯：Lisa來(lái)源：未知瀏覽：次

題解分析：

抽屜原理+同余性質(zhì)

題目等價(jià)于N個(gè)數(shù)除以L最多只有3個(gè)不同的余數(shù)，根據(jù)抽屜原理，任意選擇4個(gè)不同的數(shù) ，必定至少有兩個(gè)數(shù)a[i]和a[j]除以L的余數(shù)相同(即模L同余)。由同余的基本性質(zhì)可知abs(a[i]-a[j])必定能被L整除。

因此本題只需要從a[N]中任選4個(gè)不同的數(shù)，枚舉它們的兩兩差值(一共有 = 6 種)，對(duì)這6個(gè)數(shù)，枚舉它們的所有因子fac，進(jìn)行檢驗(yàn)（看看a[1]到a[N]除以fac是不是最多只有3個(gè)余數(shù)），符合要求則令ans+=fac。

代碼：

//抽屜原理 4個(gè)數(shù)里一定有一個(gè)相同種類(lèi)的 L一定是a[i]-a[j]的因數(shù)
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+10;
int a[N],f[N],n;
int sum=0;
void check(int x){ //檢驗(yàn)x是否合法
    vector<int> v;
    for (int i=1;i<=n;i++){
        int t=a[i]%x;
        bool pp=0;
        for (auto p:v){
            if (p==t) pp=1;
        }
        if (!pp) v.push_back(t);
        if (v.size()>3) break;
    }
    if (v.size()<=3) sum+=x;    
}
signed main(){
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    n=unique(a+1,a+n+1)-a-1;
    //排序去重
    if (n<=3){
        //3個(gè)數(shù)任意答案都合法
        int x=a[1]/4;
        cout<<(x+1)*x/2<<endl;
        return 0;
    }
    int ans=1e10,now=1;
    for (int i=1;i<=n-3;i++) {
        if (a[i+3]-a[i]<ans){
            now=i;
            ans=a[i+3]-a[i];
        }
    }
    //找到最小差值 隨便找其實(shí)也是對(duì)的
    vector<int> v;
    map<int,bool> M;
    v.push_back(a[now+1]-a[now]);
    v.push_back(a[now+2]-a[now]);
    v.push_back(a[now+3]-a[now]);
    v.push_back(a[now+2]-a[now+1]);
    v.push_back(a[now+3]-a[now+1]);
    v.push_back(a[now+3]-a[now+2]);
    for (auto vv:v){ //標(biāo)記因數(shù)
        if (vv>0){
            for (int j=1;j*j<=vv;j++)
            if (vv%j==0)
            {
                M[j]=1;
                M[vv/j]=1;
            }
        }
    }
    for (auto v:M){
        if (v.first*4<=a[1]){
            check(v.first);
        }
    }
    cout<<sum<<endl;
    return 0;
}

AP體系學(xué)生