HihoCoder 1246：王胖浩与环

#1246 : 王胖浩与环

时间限制:6000ms

单点时限:1000ms

内存限制:256MB

描述

王胖浩有一个环，环上有n个正整数。他有特殊的能力，能将环切成k段，每段包含一个或者多个数字。

对于一个切分方案，王胖浩将以如下方式计算优美程度，

首先对于每一段，求出他们的数字和。然后对于每段的和，求出他们的最大公约数，即为优美程度。

他想通过合理地使用他的特殊能力，使得切分方案的优美程度最大。

输入

第一行一个整数n，表示环上的数字个数。

接下来一行包含n个正整数，第i个数ai表示环上第i个数。

数据范围:

1<=n<=2000,1<=ai<=5*107

输出

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

样例输入

7

2 3 3 3 3 3 3

样例输出

20

5

2

2

1

1

1

官方题解：首先d一定是所有数总和的约数，这样的数并不多。接着判断一个d是否可能为k段和的约数，只要将前缀和按模d分类即可，看相同的个数是否大于等于k。

又学到了新姿势。。。一堆数的公共约数，实际上一定在 这堆数和 的约数里面找。因为很简单的道理，a%x=0 b%x=0，(a+b)是肯定%x=0的。

然后就是将约数从大到小排序，看它们在前缀和里面出现的次数，这里的做法也感觉太亮了。果然自己做题还是太少了啊。。。

代码：

#include <iostream>

#include <algorithm>

#include <cmath>

#include <vector>

#include <string>

#include <cstring>

#include <map>

#pragma warning(disable:4996)

using namespace std;

typedef long long ll;

ll n;

ll val[2005];

ll num[5000];

ll ans[2005];

int main()

{

	//freopen("i.txt","r",stdin);

	//freopen("o.txt","w",stdout);

	ll i, j, nu;

	scanf("%lld", &n);

	val[0] = 0;

	for (i = 1; i <= n; i++)

	{

		scanf("%lld", val + i);

		val[i] = val[i - 1] + val[i];

	}

	sort(val + 1, val + n + 1);

	nu = 0;

	for (i = 1; i *i <= val[n]; i++)

	{

		if (val[n] % i==0)

		{

			if (i*i == val[n])

			{

				num[nu++] = i;

				continue;

			}

			num[nu++] = i;

			num[nu++] = val[n] / i;

		}

	}

	sort(num, num + nu);

	ll temp, k, m;

	k = 1;

	for (i = nu - 1; i >= 0; i--)

	{

		temp = num[i];

		map<ll, ll>cnt;

		m = 0;

		for (j = 1; j <= n; j++)

		{

			m = max(m, ++cnt[val[j] % temp]);

		}

		while (k <= m)

		{

			ans[k] = temp;

			k++;

		}

	}

	for (i = 1; i <= n; i++)

	{

		printf("%lld\n", ans[i]);

	}

	//system("pause");

	return 0;

}