G. GCD Festival 推式子 COMPFEST 13 - Finals Online Mirror

题意

给定数组\(a\)，求

\[\sum_{i=1}^n\sum_{j=1}^ngcd(a_i,a_j) \cdot gcd(i,j) \]

\[2 \leq n \leq 10^5\\ 1 \leq a_i \leq 10^5 \]

分析

\(n = \sum_{d|n} \varphi(d)\)

\(gcd(i,j) = \sum_{d|gcd(i,j)} \varphi(d) = \sum_{d|i,d|j} \varphi(d)\)

\[\sum_{i=1}^n\sum_{j=1}^n gcd(i,j)\cdot gcd(a_i,a_j)\\ =\sum_{i=1}^n\sum_{j=1}^n gcd(a_i,a_j) \sum_{d|i,d|j} \varphi(d)\\ = \sum_{d=1}^n\varphi(d) \sum_{i=1}^{\lfloor\frac{n}{d}\rfloor} \sum_{j=1}^{\lfloor \frac{n}{d}\rfloor} gcd(a_{id},a_{jd})\\ =\sum_{d=1}^n\varphi(d) \sum_{i=1}^{\lfloor\frac{n}{d}\rfloor} \sum_{j=1}^{\lfloor \frac{n}{d}\rfloor} \sum_{k|a_{id},k|a_{jd}} \varphi(k)\\ =\sum_{d=1}^n\varphi(d) \sum_{k=1}^n \varphi(k)(\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}[a_{id} \equiv 0 (mod \ k)])^2 \]

于是可以枚举\(d\)，显然对于\(k\)只需要考虑所有\(a_{id}\)的因子，因此复杂度变为调和级数乘\(d(a_i)\)

代码

    const int maxn = 1e5 + 5;
     
    int phi[maxn];
    int v[maxn];
    vector<int> vv[maxn];
     
    inline void phi_table(int n){
        phi[1] = 1;
        for(int i = 2;i <= n;i++)
            if(!phi[i]) {
                for(int j = i;j <= n;j += i) {
                    if(!phi[j]) phi[j] = j;
                    phi[j] = phi[j] / i * (i - 1);
                }
            }
    }   
     
    int main(){
        unordered_map<int,int> mp;
        phi_table(maxn - 3);
        int n = rd();
        for(int i = 1;i <= maxn - 3;i++){
            for(int j = i;j <= maxn - 3;j += i)
                vv[j].push_back(i);
        }
        for(int i = 1;i <= n;i++){
            v[i] = rd();
        }
        int ans = 0;
        for(int d = 1;d <= n;d++){
            int tot = 0;
            mp.clear();
            for(int j = 1;j <= n / d;j++){
                for(auto it:vv[v[j * d]]) 
                    mp[it]++;
            }
            for(auto it:mp){
                add(tot,mul(phi[it.fi],(ll)it.se * it.se % MOD));
            }
            add(ans,mul(tot,phi[d]));
        }
        printf("%d",ans);
    }