解法1（DP解）

以下の説明では，$x$ の約数の個数を $\sigma(x)$ と表現します．
以下の $S$，$L$ を考えます．

$S_{i,g}$ : $A_i$が最右である連続部分列で，最大公約数が $g$ となるようなものの部分列の長さの合計

$L_{i,g}$ : $A_i$が最右である連続部分列で，最大公約数が $g$ となるようなものの個数

$S_{i,g}$ は $g$ が $A_i$ の約数でない場合は明らかに $0$ であるため， $\displaystyle \sum_{1 \leq i \leq N} \sum_{g \in {A_iの約数}} g \times S_{i,g}$ が求める答えです．よって，$S_{i,g}$ が求まっていれば，$\mathrm{O}(N \times \sigma(A_i))$ で答えを求めることができます．

次に，$S$，$L$ を求める方法を考えます．
$S$，$L$ について，以下の式が成り立ちます．

$S_{i,g} = \displaystyle \sum_{\gcd(A_i,g')=g} (S_{i-1,g'} + L_{i-1,g'})$
（ただし $g=A_i$ の場合はさらに $+1$）

$L_{i,g} = \displaystyle \sum_{\gcd(A_i,g')=g} L_{i-1,g'}$
（ただし $g=A_i$ の場合はさらに $+1$）

従って，

$S_{i,\gcd(A_i,g')}$ += $S_{i-1,g'}$ + $L_{i-1,g'}$
$L_{i,\gcd(A_i,g')}$ += $L_{i-1,g'}$

と更新することで $S_i$，$L_i$ が求まります．$S_{i-1,g'}$，$L_{i-1,g'}$ は $g'$ が $A_{i-1}$ の約数でない場合は明らかに $0$ であるため，計算量は $\mathrm{O}(\sigma(A_{i-1}) \log A_i)$ です．従って，$S$，$L$ は $\mathrm{O}(N \times \sigma(A_{i-1}) \log A_i)$ で求まります．

ここまで，ある $i$ について， $S_{i,g}$ のうち $0$ でないものを緩く $\mathrm{O}(\sigma(A_{i-1}))$ 個と見積もってきましたが，実はもう少し小さいオーダーで上から抑えることができます．$A_i$ は，$O(\log A_i)$ 個の素因数を持ちます．部分列の長さを増やしていったとき，その区間の最大公約数の素因数の種類数，素因数の数はともに単調減少します．よって， $S_{i,g}$ のうち $0$ でないものは $O(\log A_i)$ 個です．

以上より，$\mathrm{O}(N \log^2 A_i)$ で答えを求めることができます．

（解法は違いますが，類題として，$A_i$ の制約が $1 \leq A_i \leq 10^5$ と緩い代わりに，数列ではなく木上のパスで同じものを求めるabc248_gもこの機会に解いておきましょう．）

解法2（セグ木を使った解法）

testerのあぷりしあです。D問題と同じように、セグ木上の二分探索を用いて解く解法を紹介します。

以下、$g(l, r) = \gcd(A_l, A_l+1, \dots A_r)$ と定義します。
$l$ を固定して考えましょう。このとき、各 $r$ に対して、$g(l, r)$ は広義単調減少します。
$g(l, r)$ の値が減少する境目の $r$ （つまり、$g(l, r) \lt g(l, r + 1)$ を満たす $r$ ）を考えると、その個数は高々 $A[l]$ の約数の個数となります。
そこで $A[l]$ の各約数について、セグ木上の二分探索によって $r$ を求め、$r$ についてまとめて計算することでかなり計算量を改善することができます。（Dの解説も参考にしてください。） しかしながら、この計算量は $O(N \times d(A) \log N \log A)$ （$A$ は数列$A$ の任意の要素、$d(A)$ はAの約数の個数）であり、$d(A)$ が最悪で $1344$ 個もあるため間に合いません。

そこで、さらなる工夫として、境目が $r$ に対する $g(l, r)$ をすべての約数について調べるのではなく、都度更新していくことを考えます。
最初、$x = A[l]$ として、以下を境目が配列の端に到達するまで繰り返します。

1. $x$ についての $r$ を求め、$ans$ に計算値を加える。
2. $x$を、$gcd(l, r + 1)$ に更新する。

更新回数は、解法1と同様に $g(l, r)$ の素因数の個数に着目することで $\mathrm{O}(\log A)$ であることがわかります。

以上より、$\mathrm{O}(N \log N \log^2 A)$ で答えを求めることができます。

解法1のコード例（Python）

xxxxxxxxxx

import math

from collections import defaultdict

​

MOD = 1000000007

​

n = int(input())

a = [*map(int, input().split())]

​

dp = dict()

dp[a[0]] = [1,1]

ans = a[0]

for i in range(1, n):

  ndp = defaultdict(lambda: [0]*2)

  for g in dp:

    ndp[math.gcd(a[i], g)][0] += dp[g][0] + dp[g][1]

    ndp[math.gcd(a[i], g)][1] += dp[g][1]

  ndp[a[i]][0] += 1

  ndp[a[i]][1] += 1

  dp = ndp

  for g in dp:

    ans = (ans + g*dp[g][0])%MOD

print(ans)

解法2のコード例（C++）

xxxxxxxxxx

#include <bits/stdc++.h>

using namespace std;

#include <atcoder/all>

using namespace atcoder;

​

long long gcd_e() {

  return 0;

}

​

int main() {

  int n;

  cin >> n;

  vector<long long> a(n);

  for (long long &e: a) cin >> e;

​

  segtree<long long, gcd, gcd_e> seg(a);

  long long th;

  auto f = [&](long long g) {

    if (g == 0) return true;

    return g >= th;

  };

​

  modint1000000007 ans = 0;

  for (int i = 0; i < n; i++) {

    long long l, r;

    for (l = i + 1; l <= n; l = r + 1) {

      th = seg.prod(i, l);

      r = seg.max_right(i, f);

      ans += (l + r - 2 * i) * (r - l + 1) / 2 * th;

    }

  }

  cout << ans.val() << endl;

}