Div.4 爆切 爽！！！
题意解析：
对于长度为 nnn 的数组 AAA，定义 f(A)f(A)f(A) 为最后一个满足 0≤k<n0\le k\lt n0≤k<n 且 gcdi=1kAi>gcdi=1k+1Ai\gcd_{i=1}^k A_i\gt \gcd_{i=1}^{k+1} A_igcdi=1k Ai >gcdi=1k+1 Ai 的 kkk。
定义 g(A)g(A)g(A) 为重新排列数组 AAA 后 f(A)f(A)f(A) 的最大值。
给定一个长度为 nnn 的数组 AAA，请你分别求出 g([A1]),g([A1,A2]),g([A1,A2,A3]),...,g([A1,A2,...,An])g([A_1]),g([A_1,A_2]),g([A_1,A_2,A_3]),...,g([A_1,A_2,...,A_n])g([A1 ]),g([A1 ,A2 ]),g([A1 ,A2 ,A3 ]),...,g([A1 ,A2 ,...,An ]) 的值。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
注意到 fff 函数的结果 kkk 一定满足 gcdi=1k+1Ai=gcd{A}\gcd_{i=1}^{k+1} A_i=\gcd\{A\}gcdi=1k+1 Ai =gcd{A}，则题目中的 ggg 函数可以转换如下：
g(A)g(A)g(A) 表示使 AAA 数组中存在 kkk 个数的最大公约数大于 AAA 数组所有数的最大公约数的 kkk 的最大值。
显然，数组选取几个数的最大公约数，一定是整个数组的最大公约数的倍数。
那么我们可以推导出一个结论：即如果选取的数的最大公约数大于整个数组的最大公约数，那么一定存在一个质数 xxx，使选取的数的最大公约数除以整个数组的最大公约数为 xxx 的倍数。
考虑对每个数分解质因子。显然，每个数最多有一个大于 n\sqrt nn 的质因子，我们可以将这个质因子提出来单独处理，记录下剩下的质因子。
* 对于大于 n\sqrt nn 的质因子，我们可以通过 map 判断有多少个数有它，再选取其中不是 gcd\gcdgcd 的质因子的最多的那个。
* 对于剩下的，我们可以将 xxx 从 222 枚举到 n\sqrt nn ，判断有多少个 AiA_iAi 能整除 x×gcd{A}x\times \gcd\{A\}x×gcd{A}，取最值。
最终取两者最值就是答案了。
时间复杂度：O(∑n2(logn+nlogn))O(\sum n^2(\log n+\frac{\sqrt n}{\log n}))O(∑n2(logn+lognn ))。
显然不能通过，需要优化。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
优化
考虑递推处理。
对于大于 n\sqrt nn 的部分，我们注意到 gcd\gcdgcd 一定只能包含一个这个因子，所以我们可以记录下前两个最多的数，如果 gcd\gcdgcd 为最多的数的倍数，则答案为第二多的数的个数。
对于小于 n\sqrt nn 的部分，我们可以维护每个质数 xxx，有多少个 jjj 满足 Ajgcdk=1iAk\frac{A_j}{\gcd_{k=1}^{i} A_k}gcdk=1i Ak Aj 是 xxx 的倍数。
对于新增元素 AiA_iAi ：
* 如果增加后 gcd\gcdgcd 不变，则直接计算 AiA_iAi 的贡献即可。
* 如果增加后 gcd\gcdgcd 改变，则先计算 gcd\gcdgcd 变成了原先的多少分之一，然后分解质因数，对每个质因子都加上 i−1i-1i−1（因为前面的元素都有这个质因子），最后再按上面的操作即可。
最后取最大值即可。
时间复杂度：O(∑n(logn+nlogn))O(\sum n(\log n+\frac{\sqrt n}{\log n}))O(∑n(logn+lognn ))。
