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;
  template <class T>
  void read(T &x) {
    x = 0;
    char c = getchar();
    while (c > '9' || c < '0') c = getchar();
    while (c >= '0' && c <= '9') {
      x = x * 10 + c - '0';
      c = getchar();
    }
  }
  bool bo[100001];
  int p[100001], tot = 0, mu[100001], S[100001], a[100001], num[100001],
                 sum[100001], q[100001];
  int gcd(int x, int y) { return y == 0 ? x : gcd(y, x % y); }
  int main() {
    int i, j, n, ans = 0, d, t, d1, s;
    mu[1] = 1;
    bo[1] = 1;
    for (i = 2; i < 100001; ++i) {
      if (!bo[i]) {
        p[++tot] = i;
        q[tot] = 100001 / i;
        mu[i] = -1;
        for (j = 2; j * i < 100001; ++j) {
          bo[j * i] = 1;
          if (j % i) mu[j * i] = -mu[j];
        }
      }
    }
    for (i = 1; i < 100001; ++i) {
      for (j = 1; j * i < 100001; ++j) {
        S[i * j] = (1LL * S[i * j] + j * mu[i] + 1000000007) % 1000000007;
      }
    }
    read(n);
    for (i = 1; i <= n; ++i) read(a[i]);
    int m = min(800, n);
    for (d = m + 1; d <= n; ++d) {
      for (i = 1; i * d <= n; ++i) {
        for (j = 1; j * d <= n; ++j)
          ans = (ans + 1LL * S[d] * gcd(a[i * d], a[j * d])) % 1000000007;
      }
    }
    for (d = 1; d <= m; ++d) {
      memset(num, 0, sizeof(num));
      for (i = 1; i * d <= n; ++i) ++num[a[i * d]];
      for (i = 1; i <= tot; ++i) {
        for (j = q[i]; j >= 1; --j) num[j] += num[p[i] * j];
      }
      t = 0;
      for (d1 = 1; d1 < 100001; ++d1) {
        t = (t + 1LL * S[d1] * num[d1] % 1000000007 * num[d1]) % 1000000007;
      }
      ans = (ans + 1LL * t * S[d]) % 1000000007;
    }
    printf("%d\n", ans);
    return 0;
  }
  