C2>>D 有点难绷。
题意解析：
给定一个长度为 nnn 的数组 AAA 和 BBB。你可以进行任意次操作：
* 选择一个正整数 i(1≤i≤n)i(1\le i\le n)i(1≤i≤n)。
* 花费 BiB_iBi ，使 AiA_iAi 的值 +1+1+1。
求最小花费，使 AAA 存在两个数不互质。
1≤n,Ai≤2×105,1≤Bi≤1091\le n,A_i\le 2\times 10^5,1\le B_i\le 10^91≤n,Ai ≤2×105,1≤Bi ≤109。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
首先考虑已经满足条件的情况。
考虑分解质因子。如果有两个数不互质，则它们必然有至少一个质因子相同。
所以可以开个桶，枚举每一数的质因子标记在桶里，如果这个数的质因子已经出现过了，则已经满足条件了，直接输出 000。
然后我们注意到存在一种操作方法：选择两个数，把它们都变成偶数即可。
我们可以按 BiB_iBi 排序，取前两个变成偶数。这样答案的上界就确定出来了：(B1×(A1mod 2)+B2×(A2mod 2))(B_1\times (A_1\mod 2)+B_2\times (A_2\mod 2))(B1 ×(A1 mod2)+B2 ×(A2 mod2))。
显然不存在对两个或以上不同的数进行操作后的花费能低于这个上界。所以我们考虑对同一个数进行操作。
注意到按 BiB_iBi 排序后 B1≤B2≤B3≤...≤BnB_1\le B_2\le B_3\le...\le B_nB1 ≤B2 ≤B3 ≤...≤Bn ，所以对于 i≥2i\ge 2i≥2，Bi×2≥(B1+B2)≥(B1×(A1mod 2)+B2×(A2mod 2))B_i\times 2\ge (B_1+B_2)\ge (B_1\times (A_1\mod 2)+B_2\times (A_2\mod 2))Bi ×2≥(B1 +B2 )≥(B1 ×(A1 mod2)+B2 ×(A2 mod2))，要想花费低于这个上界，最多只能操作 111 次。
我们可以枚举 2≤i≤n2\le i\le n2≤i≤n，分别判断对 iii 操作一次后能否满足条件，如果能就更新答案。
那对于 i=1i=1i=1 呢？注意到 B2B_2B2 可能是 B1B_1B1 的很多倍，所以枚举操作几次就行不通了。
但是我们可以枚举 B2B_2B2 至 BnB_nBn 的所有质因子，找到使 A1A_1A1 含有这个质因子的最小操作次数。这样就能快速解决了。
这样时间复杂度是多少呢？
我们可以用埃式筛预处理出每个数的最小质因子，分解质因子时直接一直除以这个最小质因子即可。因为一个正整数 xxx 最多含有 ⌊log2x⌋\lfloor\log_2 x\rfloor⌊log2 x⌋ 个质因子，所以分解质因子是 O(nlogV)O(n\log V)O(nlogV) 的，这也是所有 AiA_iAi 质因子数量之和。
显然可以 O(nlogV)O(n\log V)O(nlogV) 判断操作一次后是否满足、求出对 i=1i=1i=1 进行操作的花费最小值，具体可以见代码。
所以总时间复杂度是 O(VloglogV+∑(nlogn+nlogV))O(V\log \log V+\sum (n\log n+n\log V))O(VloglogV+∑(nlogn+nlogV))，其中 V=2×105V=2\times 10^5V=2×105。
我爱卡常
在学校想了一会，发现还可以优化。
首先我们可以建个类似并查集的东西，快速定位到一个数不同的质因子。例如 father[6]=3,father[12]\text{father}[6] = 3, \text{father}[12]father[6]=3,father[12] 也等于 333，因为有两个相同的质因子 222。
这样分解质因子就优化到 O(nω(V))O(n\omega(V))O(nω(V)) 了。
然后也不需要对整个数组排序，只需要让前两个 BiB_iBi 最小的在前面就行了。
时间复杂度：O(VloglogV+∑nω(V))O(V\log \log V+\sum n\omega(V))O(VloglogV+∑nω(V))，其中 V=2×105V=2\times 10^5V=2×105，ω(n)\omega(n)ω(n) 表示 nnn 以内不同质因子数量最大值。
