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 = 1e5 + 5;
  vector<int> fac[MAXN];
  int prime[MAXN];
  bool flag[MAXN];
  int phi[MAXN];
  int a[MAXN];
  int tot = 0;
  int n;
  const int mod = 1e9 + 7;
  int Mul(int a, int b) { return 1ll * a * b % mod; }
  int Add(int a, int b) { return a + b >= mod ? a + b - mod : a + b; }
  int Minus(int a, int b) { return a - b < 0 ? a - b + mod : a - b; }
  void euler() {
    phi[1] = 1;
    for (int i = 2; i < MAXN; i++) {
      if (!flag[i]) {
        prime[tot++] = i;
        phi[i] = i - 1;
      }
      for (int j = 0; j < tot && 1ll * i * prime[j] < MAXN; j++) {
        flag[i * prime[j]] = 1;
        if (i % prime[j] == 0) {
          phi[i * prime[j]] = prime[j] * phi[i];
          break;
        } else {
          phi[i * prime[j]] = (prime[j] - 1) * phi[i];
        }
      }
    }
  }
  int cnt[MAXN];
  vector<int> usd;
  int cal(int x) {
    for (int i = x; i < MAXN; i += x) {
      for (auto it : fac[a[i]]) {
        cnt[it]++;
        usd.push_back(it);
      }
    }
    int res = 0;
    for (auto it : usd) {
      res = Add(res, Mul(phi[it], Mul(cnt[it], cnt[it])));
      cnt[it] = 0;
    }
    usd.clear();
    return res;
  }
  int main() {
    euler();
    for (int i = 1; i < MAXN; i++) {
      for (int j = i; j < MAXN; j += i) {
        fac[j].push_back(i);
      }
    }
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
      scanf("%d", &a[i]);
    }
    int res = 0;
    for (int i = 1; i <= n; i++) {
      res = Add(res, Mul(phi[i], cal(i)));
    }
    printf("%d", res);
    return 0;
  }
  