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>
  using namespace std;
  const int MAXN = 100005;
  const int MOD = (int)1e9 + 7;
  long long n, a[MAXN], sum_gcd[MAXN], mobius[MAXN], euler[MAXN], nxt[MAXN],
      cnt[MAXN];
  long long sum;
  vector<long long> divisor[MAXN];
  long long add(long long &a, long long b) { a = (a + b) % MOD; }
  long long sub(long long &a, long long b) { a = (((a - b) % MOD) + MOD) % MOD; }
  void update(int x, int val) {
    for (int d : divisor[x]) {
      sub(sum, euler[d] * cnt[d] * cnt[d]);
      cnt[d] += val;
      add(sum, euler[d] * cnt[d] * cnt[d]);
    }
  }
  int main() {
    for (int i = 1; i < MAXN; ++i)
      for (int j = i; j < MAXN; j += i) divisor[j].push_back(i);
    for (int i = 2; i < MAXN; ++i) {
      for (int j = i; j < MAXN; j += i) {
        if (nxt[j] == 0) nxt[j] = i;
      }
    }
    mobius[1] = 1;
    euler[1] = 1;
    for (int i = 2; i < MAXN; ++i) {
      int p = nxt[i];
      if (p == nxt[i / p]) {
        mobius[i] = 0;
        euler[i] = euler[i / p] * p;
      } else {
        mobius[i] = -mobius[i / p];
        euler[i] = euler[i / p] * (p - 1);
      }
    }
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int k = 1; k <= n; ++k) {
      for (int i = k; i <= n; i += k)
        for (auto d : divisor[a[i]]) cnt[d] += 1;
      for (int i = k; i <= n; i += k)
        for (auto d : divisor[a[i]]) {
          add(sum_gcd[k], euler[d] * cnt[d] * cnt[d]);
          cnt[d] = 0;
        }
    }
    long long ans = 0;
    for (int k = 1; k <= n; ++k) {
      add(ans, euler[k] * sum_gcd[k]);
    }
    cout << ans;
    return 0;
  }
  