# Codeforces 1575G GCD Festival
## 求$\sum_{i=1}^{n}\sum_{j=1}^{n}gcd(a_i, a_j)gcd(i, j)$, $n<10^5$, $a_i<n$, $mod\ 10^9+7$.

> https://codeforces.com/contest/1575/problem/G
>

$\forall n \in {\bf N}$, $\sum_{d|n}\phi(d) = n \Rightarrow \sum_{d|x, d|y}\phi(d) = gcd(x, y)$，
let $N=10^5$,

\begin{array}{ll}
&\sum_{i=1}^{n}\sum_{j=1}^{n}gcd(a_i, a_j)gcd(i, j) \\
=& \sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{x|i,x|j}\phi(x)gcd(a_i, a_j) \\
=&\sum_{x=1}^{N} \phi(x) \sum_{i=1}^{\lfloor n/x \rfloor} \sum_{j=1}^{\lfloor n/x \rfloor} gcd(a_{ix}, a_{jx}) \\
=&\sum_{x=1}^{N} \phi(x) \sum_{i=1}^{\lfloor n/x \rfloor} \sum_{j=1}^{\lfloor n/x \rfloor} \sum_{y|a_{ix}, y|a_{jx}} \phi(y) \\
=&\sum_{x=1}^{N} \phi(x) \sum_{i=1}^{\lfloor n/x \rfloor} \sum_{j=1}^{\lfloor n/x \rfloor} \sum_{y=1}^{N} [y|a_{ix}][y|a_{jx}] \phi(y) \\
=& \sum_{x=1}^{N} \phi(x) \sum_{y=1}^{N} \phi(y) \sum_{i=1}^{\lfloor n/x \rfloor} [y|a_{ix}] \sum_{j=1}^{\lfloor n/x \rfloor} [y|a_{jx}] \\
=& \sum_{x=1}^{N} \phi(x) \sum_{y=1}^{N} \phi(y) (\sum_{i=1}^{\lfloor n/x \rfloor} [y|a_{ix}])^2
\end{array}
發現$\sum_{y=1}^{N} \phi(y) (\sum_{i=1}^{\lfloor n/x \rfloor} [y|a_{ix}])^2$僅要對$a_{ix}$之因數枚舉就好，於是對於x，我們將數組$\{a_{ix}\}$抓出來，用$cnt[y]$紀錄有幾個數被$y$整除，這之前先$O(nlogn)$預處理1~N中之因數：

#include <bits/stdc++.h>
#pragma GCC optimize(3)
#define ll long long
#define pii pair<int, int>
#define pll pair<long long, long long>
#define F first
#define S second
#define endl '\n'
using namespace std;
const int inf = 0x3f3f3f3f;
int mod = 1e9 + 7;
const int N = 1e5 + 5;


void solve(){
    int n; cin >> n;
    ll phi[N], a[n+1];
    bool p[N];
    memset(p, 0, sizeof p);
    for(int i=1; i<=n; i++) cin >> a[i];
    for(int i=1; i<N; i++) phi[i] = i;
    for(int i=2; i<N; i++){
        if(p[i]) continue;
        for(int j=i; j<N; j+=i){
            p[j] = 1;
            phi[j] = phi[j] * (i - 1) / i;
        }
    }

    vector<vector<int>> d(N);
    for(int i=2; i<N; i++){
        for(int j=i; j<N; j+=i){
            d[j].push_back(i);
        }
    }

    ll ans = 0;
    int cnt[N];
    memset(cnt, 0, sizeof cnt);
    for(int x=1; x<=n; x++){
        for(int i=1; i*x<=n; i++){
            for(auto j : d[a[i*x]]) cnt[j]++;
        }
        ll tmp = 0;
        for(int i=1; i*x<=n; i++){
            for(auto j : d[a[i*x]]){
                tmp = (tmp + phi[j] * cnt[j] * cnt[j]) % mod;
                cnt[j] = 0;
            }
        }

        tmp = (tmp + phi[1] * (n/x) * (n/x)) % mod;
        ans = (ans + tmp * phi[x]) % mod;
    }
    cout << ans << endl;
}


int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    
    int t = 1;
    //cin >> t;
    while(t--)
    solve();
    return 0;
}

### 時間複雜度 ：$\sum_{i=1}^{\lfloor n/1 \rfloor}d(a_{i}) \ + \sum_{i=1}^{\lfloor n/2 \rfloor}d(a_{2i}) \ + \ ... \ \le 100O(nlogn)$

###### tags: `math` `number theory`