Max GCD（暴力）

题目描述

We have a sequence of N integers: A1,A2,⋯,AN.

You can perform the following operation between 0 and K times (inclusive):

·Choose two integers i and j such that i≠j, each between 1 and N (inclusive). Add 1 to Ai and −1 to

Aj, possibly producing a negative element.

Compute the maximum possible positive integer that divides every element of A after the operations. Here a positive integer x divides an integer y if and only if there exists an integer z such that

y=xz.

Constraints

·2≤N≤500

·1≤Ai≤106

·0≤K≤109

·All values in input are integers.

输入

Input is given from Standard Input in the following format:

N K

A1 A2 ⋯ AN−1 AN

输出

Print the maximum possible positive integer that divides every element of A after the operations.

样例输入

【样例1】

2 3

8 20

【样例2】

2 10

3 5

【样例3】

4 5

10 1 2 22

【样例4】

8 7

1 7 5 6 8 2 6 5

样例输出

【样例1】

7

【样例2】

8

【样例3】

7

【样例4】

5

提示

样例1解释

7 will divide every element of A if, for example, we perform the following operation:

·Choose i=2,j=1. A becomes (7,21).We cannot reach the situation where 8 or greater integer divides every element of A.

样例2解释

Consider performing the following five operations:

·Choose i=2,j=1. A becomes (2,6).

·Choose i=2,j=1. A becomes (1,7).

·Choose i=2,j=1. A becomes (0,8).

·Choose i=2,j=1. A becomes (−1,9).

·Choose i=1,j=2. A becomes (0,8).

Then, 0=8×0 and 8=8×1, so 8 divides every element of A. We cannot reach the situation where 9 or greater integer divides every element of A.

思路

每次操作后，实际上a的总和不变，因此若存在x能整除a的总和，那么即可以以该数作为因子求解，暴力枚举[1,sum]，若x求解后符合条件，则该x成立

代码实现

#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=505;
const int M=20;
const int INF=0x3f3f3f;
const ull sed=31;
const ll mod=1e9+7;
const double eps=1e-8;
const double PI=acos(-1.0);
typedef pair<int,int>P;
 
int n,a[N],k,sum,temp[N];
 
bool judge(int x)
{
    if(sum%x) return false;
    for(int i=1;i<=n;i++) temp[i]=a[i]%x;
    sort(temp+1,temp+1+n);
    int l=1,r=n,op=0;
    while(l<r)
    {
        if(temp[l]%x==0)
        {
            l++;
            continue;
        }
        if(temp[r]%x==0)
        {
            r--;
            continue;
        }
        int t=min(temp[l]%x,x-(temp[r]%x));
        temp[l]-=t;
        temp[r]+=t;
        op+=t;
    }
    return op<=k;
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        sum+=a[i];
    }
    for(int i=sum;i>=1;i--)
    {
        if(judge(i))
        {
            printf("%d\n",i);
            break;
        }
    }
    return 0;
}