CF1900D 题解

· · 题解

VP 的时候没切，真的太菜了。

容易想到将数组排序，枚举两个数，然后算 \gcd，第三个数的位置是可以求的，这样容易求得 ans，可惜时间复杂度 \mathcal{O}(n^2)，无法通过本题。

首先我们需要知道一个常识：一个数的因数不会很多，好像我以前做的一道题中 5\times 10^5 以内因数最多的也只有 240 个（数字可能不准确，请打表验证）。上面这个常识是感觉和因数有关的题需要积累的，这种题多做几遍就会了。

所以，我们可以预处理出一个数的因数，并且把 a 数组正序排序。

对于一个 i 如果我知道 i 和前面的数组成 \gcd 的和 sum，那么就可以知道对答案的贡献就是 sum\times(n-i)，现在需要求 sum。

怎么求 sum，考虑容斥。

在处理 1\sim i-1 的时候，我们可以处理出对于一个数 x，一个数的因数为 x 这个数的个数。

那么在处理第 i 项的时候，我们对于它的一个因数 x，要求恰好 \gcd 为 j 的个数，记为 g_j。

显然，g_j\le f_j。

那么 g_j 可以从 f_j 开始，减去 g_{2j},g_{3j}\dots，注意减去的这些数的下标也需要满足是 a_i 的因数，这样才说明 j 是 a_i 和另外某一个数的 \gcd。

容斥解决。

注意这里每一个数的因数需要倒序取出，这样才可以保证取 g_i 的时候 g_{2i} 等已经处理好了。

代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 8e4 + 5, M = 1e5 + 5, maxn = 1e5;
int T, n, a[N], f[M], tem, cnt, ans, qp[M][32], tot, g[M];
vector<int>num[M], c;
inline void init(){
    for(int i = 1; i <= maxn; i++) f[i] = g[i] = 0ll;
    ans = 0ll;
}
inline int get(int x, int val){
    int res = 0;
    for(auto xx : num[val / x]){
        if(xx != 1) g[x] -= g[x * xx];
    }
    return g[x];
}
inline void solve(){
    for(int i = 1; i < n; i++){
        cnt = 0ll;
        for(auto x : num[a[i]]){
            g[x] = f[x];
            cnt += get(x, a[i]) * x;
        }
        for(auto x : num[a[i]]){
            f[x]++;
        }
//      printf("%d %d\n", i, cnt);
        cnt *= (n - i);
        ans += cnt;
    }
}
inline bool cmp(int x, int y){
    return x > y;
}
signed main(){
    scanf("%lld", &T);
    for(int i = 2; i <= maxn; i++){
        qp[i][0] = 1;
        for(int j = 1; qp[i][j - 1] <= maxn; j++){
            qp[i][j] = qp[i][j - 1] * i;
        }
    }
    num[1].push_back(1);
    for(int i = 2; i <= maxn; i++){
        tem = i;
        tot = 0;
        num[i].push_back(1ll);
        for(int j = 2; j * j <= i; j++){
            if(tem % j) continue ;
            cnt = 0;
            while(tem % j == 0){
                cnt++;
                tem /= j;
            }
            c = num[i];
            for(auto x : c){
                for(int kk = 1; kk <= cnt; kk++){
                    num[i].push_back(x * qp[j][kk]);
                }
            }
        }
        if(tem > 1){
            c = num[i];
            for(auto x : c){
                num[i].push_back(tem * x);
            }
        }
        sort(num[i].begin(), num[i].end(), cmp);
    }
    while(T--){
        init();
        scanf("%lld", &n);
        for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
        sort(a + 1, a + n + 1);
        solve();
        printf("%lld\n", ans);
    }
    return 0;
}

评测链接