Пусть \(a\), \(b\) и \(c\) — целые числа. Определим функцию \(f(a, b, c)\) следующим образом.
Упорядочить числа \(a\), \(b\), \(c\) таким образом, чтобы выполнялось \(a \le b \le c\). Затем вернуть \(\gcd(a, b)\), где \(\gcd(a, b)\) обозначает наибольший общий делитель (НОД) чисел \(a\) и \(b\).
Иными словами, мы берем \(\gcd\) из \(2\) меньших значений и игнорируем наибольшее.
Вам дан массив \(a\) длины \(n\). Вычислите сумму \(f(a_i, a_j, a_k)\) для всех \(i\), \(j\), \(k\) таких, что \(1 \le i < j < k \le n\).
Более формально, вычислите \(\)\sum_{i = 1}^n \sum_{j = i+1}^n \sum_{k =j +1}^n f(a_i, a_j, a_k).\(\)
Выходные данные
Для каждого набора входных данных выведите одно число — сумму из условия.
Примечание
В первом наборе входных данных значения \(f\) следующие:
- \(i=1\), \(j=2\), \(k=3\), \(f(a_i,a_j,a_k)=f(2,3,6)=\gcd(2,3)=1\);
- \(i=1\), \(j=2\), \(k=4\), \(f(a_i,a_j,a_k)=f(2,3,12)=\gcd(2,3)=1\);
- \(i=1\), \(j=2\), \(k=5\), \(f(a_i,a_j,a_k)=f(2,3,17)=\gcd(2,3)=1\);
- \(i=1\), \(j=3\), \(k=4\), \(f(a_i,a_j,a_k)=f(2,6,12)=\gcd(2,6)=2\);
- \(i=1\), \(j=3\), \(k=5\), \(f(a_i,a_j,a_k)=f(2,6,17)=\gcd(2,6)=2\);
- \(i=1\), \(j=4\), \(k=5\), \(f(a_i,a_j,a_k)=f(2,12,17)=\gcd(2,12)=2\)
- \(i=2\), \(j=3\), \(k=4\), \(f(a_i,a_j,a_k)=f(3,6,12)=\gcd(3,6)=3\);
- \(i=2\), \(j=3\), \(k=5\), \(f(a_i,a_j,a_k)=f(3,6,17)=\gcd(3,6)=3\);
- \(i=2\), \(j=4\), \(k=5\), \(f(a_i,a_j,a_k)=f(3,12,17)=\gcd(3,12)=3\);
- \(i=3\), \(j=4\), \(k=5\), \(f(a_i,a_j,a_k)=f(6,12,17)=\gcd(6,12)=6\).
Сумма по всем тройкам равна
\(1+1+1+2+2+2+3+3+3+6=24\).
Во втором наборе входных данных существует \(56\) способов выбора значений \(i\), \(j\), \(k\). Сумма по всем \(f(a_i,a_j,a_k)\) равна \(203\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
5
2 3 6 12 17
8
6 12 8 10 15 12 18 16
|
24
203
|