Екстремум Ейлера#4107

Екстремум Ейлера (Розбір)

Перепишемо вказану суму $H$ наступним чином:

φ (1) \cdot φ (1) + φ (1) \cdot φ (2) + ... + φ (1) \cdot φ (n) + φ (2) \cdot φ (1) + φ (2) \cdot φ (2) + ... + φ (2) \cdot φ (n) + ... φ (n) \cdot φ (1) + φ (n) \cdot φ (2) + ... + φ (n) \cdot φ (n)

φ(1) \cdot φ(1) + φ(1) \cdot φ(2) + ... + φ(1) \cdot φ(n) + \\ φ(2) \cdot φ(1) + φ(2) \cdot φ(2) + ... + φ(2) \cdot φ(n) + \\ . . . \\ φ(n) \cdot φ(1) + φ(n) \cdot φ(2) + ... + φ(n) \cdot φ(n)

Згрупуємо доданки в сумі $H$ за спільним множником:

φ (1) \cdot (φ (1) + φ (2) + \dots φ (n)) + φ (2) \cdot (φ (1) + φ (2) + \dots φ (n)) + ... φ (n) \cdot (φ (1) + φ (2) + \dots φ (n))

φ(1) \cdot (φ(1) + φ(2) + … φ(n)) + \\ φ(2) \cdot (φ(1) + φ(2) + … φ(n)) + \\ . . . \\ φ(n) \cdot (φ(1) + φ(2) + … φ(n))

У всіх доданках присутній один і той самий множник. Винесемо його за дужки:

H = (φ (1) + φ (2) + \dots φ (n))^{2}

H = (φ(1) + φ(2) + … φ(n))^2

Реалізуємо решето, яке обчислить всі значення функції Ейлера від $1$ до $1 0^{4}$ 10^4 і збереже їх у масиві $f i$ . Потім побудуємо масив часткових сум $s u m$ , де

s u m [i] = φ (1) + φ (2) + ... + φ (i)

sum[i] = φ(1) + φ(2) + ... + φ(i)

Після цього для кожного вхідного значення $n$ виведемо добуток

s u m [n] \cdot s u m [n]

sum[n] \cdot sum[n]

Приклад

Розглянемо стан масиву значень функції Ейлера $f i$ та масиву часткових сум $s u m$ :

Для $n = 10$ n = 10 відповідь дорівнює

(φ (1) + φ (2) + \dots φ (10))^{2} = s u m [10]^{2} = 3 2^{2} = 1024

(φ(1) + φ(2) + … φ(10))^2 = sum[10]^2 = 32^2 = 1024

Реалізація алгоритму

Оголосимо робочі масиви $f i$ та $s u m$ , де

$f i [i] = φ (i)$ fi[i] = φ(i);
$s u m [i] = φ (1) + φ (2) + ... φ (i)$ sum[i] = φ(1) + φ(2) + ... φ(i)

#define MAX 10001
long long fi[MAX], sum[MAX];

Функція FillEuler заповнює масив $f i$ значеннями функції Ейлера:

f i [i] = φ (i) для всіх 1 \leq i 0 ˘ 03 c M A X

fi[i] = φ(i)~для~всіх~1 ≤ i \u003c MAX

void FillEuler(void)
{
  int i, j;
  for (i = 0; i \u003c MAX; i++) fi[i] = i;
  for (i = 2; i \u003c MAX; i++)
    if (fi[i] == i)
      for (j = i; j \u003c MAX; j += i)
        fi[j] -= fi[j] / i;

C++

Обчислюємо часткові суми $s u m [i]$ . Ініціалізуємо перші елементи масиву.

  sum[0] = 0; sum[1] = 1;

Потім послідовно обчислюємо решту часткових сум.

  for(i = 2; i \u003c MAX; i++)
    sum[i] = sum[i-1] + fi[i];
}

Основна частина програми. Заповнюємо масиви $f i$ та $s u m$ .

FillEuler();

Обробляємо $t es t s$ тестів.

scanf("%d",\u0026tests);
while(tests--)
{
  scanf("%d",\u0026n);

Для кожного вхідного значення $n$ обчислюємо і виводимо відповідь

s u m [n] \cdot s u m [n] = (φ (1) + φ (2) + \dots φ (n))^{2}

sum[n] \cdot sum[n] = (φ(1) + φ(2) + … φ(n))^2

  res = sum[n] * sum[n];
  printf("%lld\n",res);
}