地盘划分
想说暴力思路对于任意两个\(a\)和\(b\)，当\(a<b\)时，可以发现最大的正方形应该是\(a\times a\)。既然题目要让每一个正方形最大，那么就可以直接用刚刚的方法来解决这一题直到最短的一条边为\(0\)。
这个思路的的时间复杂度时\(O(n)\)可以获得\(50\)分。
这个思路的问题是重复的次数太多了，那么只用把重复次数减少即可。首先可以发现\(b\)最后的结果就会使\(b%a\),可以发现这很像求最大公因数的辗转相除法所以说可以模拟辗转相处法，让\((a,b)\)变成\((a,b%a)\)。那么此时的复杂度就是\(O(log_b)\)，因为\(b\)每一次至少都变成原来的一半。
涂山之约
首先对于一个区间\([i..j]\)，可以考虑用前缀和来判断糖果数量和是否是\(3\)的倍数。这个方法的时间复杂的是\(n^2\)的。
对于任意一个右端点之只要其前缀和\(%=a_i\),那么只要此时的\(sum%3\)的余数也是\(a_i\)那么答案就应该加上相同余数的的左端点个数
明月楼高休独倚
考虑以每一行为底边的矩阵
因为可以任意移动列，可以将以这一行为底座，向上延申的 的个数从大到小排序
假设第 列向上延申了\(x\) 个，那么它左边的列向上延申应该大于等于 \(x\)个
可以得出\(ans=max(ans,k*x)\)
在其中取最大值
数组统计
对于\(30%\)的数据：
对于每个数字枚举自己的因子，时间复杂度\(O(n\sqrt a_i)\)
对于\(60%\)的数据：
将枚举因子改为枚举倍数，将贡献加在倍数上，变成调和级数\(O(nlogn)\)
对于 的数据：
数字的出现次数，最多有\(O(\sqrt n)\)种不同的数字。
所以实际上只有\(O(\sqrt n)\)个数字需要讨论，对这些数字枚举因子统计可以做\(O(\sqrt n\times \sqrt a_i)\)