Codeforces Round 911 (Div. 2) |
---|
Закончено |
Пусть $$$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).$$$$$$
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$3 \le n \le 8 \cdot 10^4$$$) — длину массива $$$a$$$.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^5$$$) — элементы массива $$$a$$$.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$8 \cdot 10^4$$$.
Для каждого набора входных данных выведите одно число — сумму из условия.
252 3 6 12 1786 12 8 10 15 12 18 16
24 203
В первом наборе входных данных значения $$$f$$$ следующие:
Во втором наборе входных данных существует $$$56$$$ способов выбора значений $$$i$$$, $$$j$$$, $$$k$$$. Сумма по всем $$$f(a_i,a_j,a_k)$$$ равна $$$203$$$.
Название |
---|