CODEFORCES 2148G FARMER JOHN'S LAST WISH 题解
原题链接：HTTPS://CODEFORCES.COM/PROBLEMSET/PROBLEM/2148/G
一、题目大意
给你一个数组前缀：[a1,a2,…,ai][a_1,a_2,\dots,a_i][a1 ,a2 ,…,ai ]。
你可以随便重新排列这 iii 个数。
我们定义：
* 从左到右看前缀的 gcd（最大公约数）会越来越小或不变。
* 如果在某个位置 kkk：
gcd(a1,…,ak)>gcd(a1,…,ak+1)\gcd(a_1,\dots,a_k) > \gcd(a_1,\dots,a_{k+1}) gcd(a1 ,…,ak )>gcd(a1 ,…,ak+1 )
说明在加上第 k+1k+1k+1 个数时，gcd 真的变小了。
题目要你对每个前缀，求出：
通过最好的重排，能让“最后一次 gcd 变小”发生得尽量靠后，也就是最大的 kkk。
输出每个前缀的答案。
二、思考方向
想让“最后一次 gcd 下降”尽量靠后，意味着：
* 前面尽量多放一些“很合得来”的数（gcd 不会被破坏）。
* 直到最后某一步，放一个“不合群”的数，gcd 才下降。
所以我们只需要考虑两种“答案的产生方式”：
情况 A：新来的数当“破坏者”
如果当前前缀整体 gcd 在加入新数后变小了，那么说明：
* 你可以把新数放到最后
* 前面 i−1i-1i−1 个先摆好让 gcd 不变
* 最后这个数一放进去，gcd 降低
因此答案至少可以是：i-1
情况 B：新来的数当“合群者”
如果我们希望最后一次下降发生在更后面，那前面这段必须有 gcd = 某个 ddd（d>1d>1d>1），并且：
* 前面这段里所有数都能被 ddd 整除（它们“合群”）
* 但整个前缀里至少有一个数不能被 ddd 整除（这样 gcd 才能在后面被“破坏”）
所以对于每个可能的 ddd（它必须是某些数的因数），我们只要数：
* 当前前缀中，有多少个数是 ddd 的倍数（记作 cnt[d]）
* 如果 cnt[d] != i（不是所有数都能被 ddd 整除），那就说明可以安排：
* 先放这 cnt[d] 个倍数（前缀 gcd 至少是 ddd）
* 再放一个不是倍数的数（gcd 会下降）
* 所以答案可以取 cnt[d]
最终每个前缀答案就是：
* max( i-1（情况A）, 所有可行的 cnt[d]（情况B） )
三、解题思路
我们从左到右处理前缀。
维护：
1. nowgcd：当前前缀的整体 gcd
2. f[d]：当前前缀里，有多少个数能被 ddd 整除（即 ddd 的倍数个数）
3. ans：当前前缀的答案
处理第 iii 个数 x：
1）更新所有因数的计数
枚举 x 的所有因数 d：
* f[d]++
* 如果 f[d] != i说明前缀里还有别的数不是 d 的倍数
* 那么 d 是可行的 gcd 候选
* 更新 ans = max(ans, f[d])
2）检查“破坏者”情况
如果 gcd(nowgcd, x) 变小了（不等于 nowgcd）：
* 说明 x 可以作为最后的破坏者
* 更新 ans = max(ans, i-1)
3）输出答案，更新 NOWGCD
* 输出 ans
* nowgcd = gcd(nowgcd, x)
因数怎么快速枚举？
提前预处理 yin[v]：存 v 的所有因数。
用类似筛法：对每个 i，把它加到所有倍数 j 的因数表里。
复杂度大概是 O(nlogn)O(n \log n)O(nlogn)，能过。
四、完整代码
