题目

题目描述

小A有一个环，环上有$n$个正整数
他有特殊的能力（？？？），能将环切成$k$段，每段包含一个或者多个数字
对于一个切分方案，小A将以如下方式计算优美程度：
首先对于每一段，求出他们的数字和
然后对于每段的和，求出他们的最大公约数，即为优美程度
他想通过合理地使用他的特殊能力，使得切分方案的优美程度最大

输入格式

第一行一个整数$n$，表示环上的数字个数
接下来一行包含$n$个正整数，第$i$个数$a_i$表示环上第$i$个数

输出格式

输出$n$行，第$i$行表示切成$i$段时的最大优美程度

样例

样例输入

1 2	7 2 3 3 3 3 3 3

样例输出

数据范围与提示

对于$20\%$的数据，$n \leqslant 16,a_i \leqslant 10$
对于$40\%$的数据，$n \leqslant 100,a_i \leqslant 1000$
对于$100\%$的数据，$n \leqslant 2000,1 \leqslant a_i \leqslant 5 \times 10^7$

题解

显然，答案是$\sum \limits_{i=1}^na_i$的约数
所以我们可以枚举$\sum \limits_{i=1}^na_i$的每一个约数，对于每一个约数$d$，计算最多能切成几段，使得这几段$gcd$起来是$d$
现在的问题就是到底能分成几段
这个非常简单
我们统计前缀和$sum_i$，如果$sum_i\equiv sum_j\pmod{d}$，那么$i\sim j$就可以分一段
所以，我们可以用一个map统计$sum_i$模$d$的余数，然后答案就是这个map中值最大的那个
最终的答案就是后缀最大值啦！
附上代码：

#include<cstdio>
#include<cmath>
#include<map>
using namespace std;
int n;
long long a[2010],ans[2010];
map<long long,int> mod;
void work(long long k)
{
    mod.clear();
    for(int i=1,s;i<=n;i++) s=++mod[a[i]%k],ans[s]=max(ans[s],k);
}
int main()
{
    freopen("circle.in","r",stdin);
    freopen("circle.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]),a[i]+=a[i-1];
    for(long long i=1;i<=sqrt(a[n]);i++) if(!(a[n]%i)){
        work(i);
        if(i*i!=a[n]) work(a[n]/i);
    }
    for(int i=n;i;i--) ans[i]=max(ans[i],ans[i+1]);
    for(int i=1;i<=n;i++) printf("%lld\n",ans[i]);
}