题目大意

$n$（$1\le n\le 2000$）个正整数 $a_1, a_2, \dots, a_n$（$a_i\le 5\times 10^7$）分布在一个圆环上。
定义 $b_k$ 为：将环上的数划分成 $k$ 段，每段上的数之和的 GCD 的最大值。
求 $b_1, b_2, \dots, b_n$ 。

解法

首先，不难看出， $b_k$ 是 $n$ 个数之和 （记做 $S$）的约数。
考虑到 $S$ 的约数并不多（$2\sqrt{n}$ 是很松的上界，并且往往 $n$ 越大这上界越松），从而可以考虑枚举 $S$ 的约数 $d$，问题转化为

这 $n$ 个数最多能分成几段，使得每段数之和都能被 $d$ 整除。

算法一

枚举分段的起始位置 $i$，以 $i$ 为序列起点求前缀和，看前缀和中有几个能被 $d$ 整除。
复杂度 $O(n^2)$

算法二

不必枚举分段的起点。
对输入序列求前缀和。
按模 $d$ 的余数将 $n$ 个前缀和分类，用 std::unordered_map<int,int>，记录每个类中有多少个前缀和。
最大的类的 size 即为所求。

复杂度 $O(n\log n)$

这个做法应该是老套路了，我却不知道，我太菜了。TAT

最新文章

1. C语言-Hello, world
2. Number of Digit One
3. ping: sendto: Network is unreachable
4. html插入链接
5. 分布式缓存（Cache）
6. mysql btree与hash索引的适用场景和限制
7. iOS开发之 Xcode svn更新代码后，不能打开.xcodeproj，因为该项目文件不能被解析
8. C#判断字符串为空
9. Python中http请求方法库汇总
10. 刺猬大作战（游戏引擎用Free Pascal写成，GUI用C++写成，使用SDL和Qt4）
11. javascript高级知识点——继承
12. 【已解决】谁动了我的CurrentPrincipal？求助我在给Artech的wcf petshop增加授权机制的时候遇到的问题。
13. CentOS6.4安装go环境
14. 未来工厂——电器行业ERP案例
15. Android插件化的思考——仿QQ一键换肤,思考比实现更重要！
16. 通过Ajax来简单的实现局部刷新（主要为C#中使用的UpdatePanel控件和ScriptManager控件）
17. 【清北学堂2018-刷题冲刺】Contest 9
18. 使用 DirectX 创建 3D 图形
19. linux 常用命令-ps(process state)
20. nginx php-fpm安装配置(转)

热门文章

1. UVA11212 EditingaBook （ IDA*搜索）
2. [课堂总结]C++课堂总结（二）
3. ubuntu18.04 安装五笔拼音
4. 解决TS报错Property 'style' does not exist on type 'Element'
5. Linux centos 6 配置php环境，扩展redis
6. iOSAES加密的实现
7. 20181111 计时器影响DOM点击事件的逻辑
8. ubuntu16.04安装 java JDK8
9. 好久没写了，总结一下lnux常用的命令（基础）
10. (转)webView清除缓存