description: Mr. Chanek has an array a of n integers. The prettiness value of a is denoted as:
  
  $$$∑_{i=1}^{n} {∑_{j=1}^{n} {\gcd(a_i, a_j) ⋅ \gcd(i, j)}}$$$
  
  where \gcd(x, y) denotes the greatest common divisor (GCD) of integers x and y.
  
  In other words, the prettiness value of an array a is the total sum of \gcd(a_i, a_j) ⋅ \gcd(i, j) for all pairs (i, j).
  
  Help Mr. Chanek find the prettiness value of a, and output the result modulo 10^9 + 7!
  
  Input
  
  The first line contains an integer n (2 ≤ n ≤ 10^5).
  
  The second line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 10^5).
  
  Output
  
  Output an integer denoting the prettiness value of a modulo 10^9 + 7.
  
  Example
  
  Input
  
  
  5
  3 6 2 1 4
  
  
  Output
  
  
  77
solution: #include <bits/stdc++.h>
  const long long INF = 1000000001;
  const long long MOD = 1000000007;
  using namespace std;
  vector<vector<long long>> del;
  vector<long long> was, num;
  long long C = 0;
  long long sum_gcd_fast(vector<long long> &a, long long cnt) {
    vector<long long> all;
    for (long long q : a) {
      for (long long q1 : del[q]) {
        if (was[q1] != cnt) {
          was[q1] = cnt, num[q1] = 0;
          all.push_back(q1);
        }
        num[q1]++;
      }
    }
    for (long long q : all) {
      num[q] = num[q] * num[q];
    }
    sort(all.rbegin(), all.rend());
    long long ans = 0;
    for (long long q : all) {
      ans += num[q] * q;
      for (long long q1 : del[q]) {
        num[q1] -= num[q];
      }
    }
    return ans;
  }
  void prepare() {
    del.resize(C), was.assign(C, -1), num.assign(C, 0);
    for (long long q = 1; q < C; q++) {
      for (long long q1 = q; q1 < C; q1 += q) {
        del[q1].push_back(q);
      }
    }
  }
  signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    long long n;
    cin >> n;
    C = n + 1;
    vector<long long> a(n + 1);
    for (long long q = 1; q <= n; q++) {
      cin >> a[q];
      C = max(C, a[q] + 1);
    }
    prepare();
    vector<long long> sums(n + 1);
    long long cnt = 0;
    for (long long q = 1; q <= n; q++) {
      vector<long long> now;
      for (long long q1 = q; q1 <= n; q1 += q) {
        now.push_back(a[q1]);
      }
      sums[q] = sum_gcd_fast(now, cnt++);
    }
    long long ans = 0;
    for (long long q = n; q > 0; q--) {
      ans += sums[q] % MOD * q % MOD;
      for (long long q1 : del[q]) {
        if (q1 != q) {
          sums[q1] -= sums[q];
        }
      }
    }
    cout << ans % MOD << '\n';
    return 0;
  }
  