arc122D

题意

Link

sol

贪心思路显然，我们先把选一定没事的放在后面，接下来化归成子问题。

什么时候选一定没事，也就是 \(a_i\) 具有一个质因子 \(p\),使得 \(p\) 在 \(a_i\) 中次数最高。

形式化表示：设 \(a_i=\prod_{k}p_k^{\alpha_{i,k}}\)。

那么 \(a_i\) 选一定没事，当且仅当 存在 \(k\) , \(\forall j\not = i,\alpha_{i,k}>\alpha_{j,k}\)。

因为 \(a_i\) 放在后面不会使前面的子问题更劣，所以贪心正确，如果不存在这样的 \(a_i\) ，说明这个序列 \(a\) 无解，，这里可以反证，考虑最后一个数。

那么如何判断 \(a_i\) 是否拥有最大质因子呢？

考虑对于 \(a,b,a=\prod p_i^{\alpha_i}\), \(b=\prod p_i^{\beta_i}\) ,我们想求: \(k=\prod p_i^{\alpha_i}(\alpha_i>\beta_i)\)。

给出一个较简单的方法。

求出 \(\gcd(a,b)\),我们看 \(\frac{a}{\gcd(a,b)}\) 有多少因子在 \(\gcd(a,b)\) 中，那么递归做 \(\gcd\) 即可。

可见代码。

inline int calc(int a,int b){
    int G=gcd(a,b);
    a/=G;
    int res=a;
    while(1){
        int g=gcd(res,G);
        if(g==1) break;
        G/=g,a*=g;
    }
    return a;
}

有一点值得注意，因为我们相当是把 \(\gcd(a,b)\) 拆分成 \(a\) 的因子，\(b\) 的因子两部分，所以当算出一次 \(\gcd\) 时要把 \(G\leftarrow \frac{G}{\gcd}\).

全部代码 code