Обозначим sum(g(i), f(i)) - сумму f(i) по всем i, для которых выполняется условие g(i). А p ** s - p в степени s. Нам нужно найти s(n) = sum(1 <= i < n, sum(i + 1 <= j <= n, gcd(i, j))). Пусть f(n) = sum(1 <= i <= n, gcd(i, n)), тогда: s(n) = sum(2 <= i <= n, f(i) - gcd(i, i)) = sum(2 <= i <= n, f(i) - i). f(n) = sum(1 <= i <= n, i * Q(n, i)), где Q(n, i) - количество j: 1 <= j <= n, что gcd(n, j) = i. Если n не делится на i, то Q(n, i) = 0. Иначе gcd(n, j) = i и gcd(n/i, j/i) = 1; Так как 1 <= j/i <= n/i, то Q(n, i) = phi(n), где phi(n) - количество j: 1 <= j <= n, gcd(n, j) = 1 - функция Эйлера. Пусть phi(1) = 1. Если gcd(a, b) = 1, phi(a * b) = phi(a) * phi(b). Действительно, каждое число j взаимно простое с a * b - взаимно просто с a и b. Для каждых 0 <= a' < a, 0 <= b' < b - найдется 0 <= x <= a * b: x = a' (mod a), x = b' (mod b). a' + k * a = b' + l * b, всегда имеет решение (gcd(a, b) = 1). phi(p ** s) = p ** s - p ** (s - 1), где p - простое, s > 0. Это следует из того, что gcd(j, p ** s) != 1 тогда и только тогда, когда p|j, таких j - p ** (s - 1), а всего чисел p ** s. f(n) = sum(d|n, d * Q(n, d)) = sum(d|n, d * phi(n / d)) = sum(d|n, (n / d) * phi(d)). Пусть gcd(p, n) = 1. Тогда f(n * (p ** s)) = sum(d|(n * (p ** s)), ((n * (p ** s)) / d) * phi(d)) = (p ** s) * sum(d|n, (n / d) * (phi(d) + phi(d * p) + ... + phi(d * (p ** s)))) = (p ** s) * sum(d|n, (n / d) * phi(d)) * (phi(1) + phi(p) + ... + phi(d * (p ** s))) = (p ** s) * (phi(1) + phi(p) + ... + phi(d * (p ** s))) * f(n) = (p ** s) * (1 + sum(1 <= i <= s, 1 - 1 / p)) * f(n) = (p ** s) * (s + 1 - s / p) * f(n). Для быстрого вычисления этого найдем div[n], f[n], sum[n] - простой делитель n, f(n), ответ к задаче для n соответственно. div[] вычислим с помощью решета Эратосфена: последовательно будет заполнять div[], если на какой-то итерации div[i] = 0 - i - простое. Тогда все числа i, i+i, ... k*i <= maxN - делятся на i, и мы отметили ВСЕ числа <= maxN, делящиеся на i. Иначе (div[i] > 0) простой делитель уже есть. Время работы этой части = (sum(1 <= k <= n и k - простое, n/k)) + o(1) = n * (sum(1 <= k <= n и k - простое, 1 / k) + o(1)) = w(n), где n = maxN. f[n] вычислим последовательно с помощью div[n]. Пусть p = div[n], будет делить на p, пока можно, найдем s, останется t: t * (p ** s) = n. Воспользуемся формулой. Каждое число p будет делить числа от 1 до n = o(1) + n / p + n / (p ** 2) + n / (p ** 3) + ... = n * (1 / (p - 1)) + o(1) = n / (p - 1) + o(1) Тогда все простые будут делить n * (sum(1 <= k <= n и k - простое, 1 / (k - 1)) + o(1)) = w(n), где n = maxN. sum[] просто: sum[i] = sum[i - 1] + f[i] - i. За O(n). Получаем w(n) + O(n) = w(n) + o(1). Найдет w(n): pi(n) ~ n / ln(n) - количество простых чисел <= n. p_n - n-ое простое число ~ n * ln(n). w(n) ~ n * sum(1 <= i <= n / log(n), 1 / (i * ln(i))) * (1 + o(1)). Пусть a_n = sum (1 <= i <= n, 1 / (i * ln(i))), b_n = ln(ln(n)). Докажем, что a_n / b_n = 1 + o(1). Тем самым покажем, что w(n) = n * ln(ln(n / ln(n))) * (1 + o(1)) = n * (ln(ln(n) - ln(ln(n)))) * (1 + o(1)) = n * ln(ln(n) * (1 + o(1))) * (1 + o(1)) = n * (ln(ln(n)) + ln(1 + o(1))) * (1 + o(1)) = n * ln(ln(n)) * (1 + o(1)). По теореме Штольца, если (a_(n+1)-a_(n))/(b_(n+1)-b_(n)) = c_n = 1 + o(1), то a_n/b_n = 1 + o(1). Получаем c_n = 1 / ((n + 1) * ln(n + 1) * ln(1 + (ln(n + 1) - ln(n)) / ln(n))) = (1 + o(1)) / ((n + 1) * ln(n + 1) * (ln(n + 1) - ln(n)) / ln(n)) = (1 + o(1)) / ((n + 1) * ln(1 + 1 / n)) = (1 + o(1)) / ((n + 1) / n) = 1 + o(1), что и требовалось доказать. Получаем решение за O(maxN * ln(ln(maxN)) + K) по времени (K запросов) и O(maxN) по памяти (очевидно).