Проблема Лонгге (Розбір)

Теорема. Якщо функція $f (n)$ мультиплікативна, то сумарна функція

S_{f} (n) = d ∣ n \sum f (d)

S_f(n) = \sum_{d \mid n} f(d)

також мультиплікативна.

► Нехай $x, y \in N$ x, y \in N, причому $x$ і $y$ взаємно прості.

Нехай $x_{1}, x_{2}, ..., x_{k}$ x_1, x_2, ..., x_k — всі дільники $x$ , а $y_{1}, y_{2}, ..., y_{m}$ y_1, y_2, ..., y_m — всі дільники $y$ .

Оскільки $x$ і $y$ взаємно прості, будь-який дільник $x_{i}$ x_i взаємно простий з будь-яким дільником $y_{j}$ y_j. Тому $НСД (x_{i}, y_{j}) = 1$ НСД(x_i, y_j) = 1. Це означає, що добуток $x_{i} \cdot y_{j}$ x_i \cdot y_j є дільником числа $x \cdot y$ x \cdot y.

Більше того, кожен добуток $x_{i} \cdot y_{j}$ x_i \cdot y_j дає окремий дільник числа $x \cdot y$ x \cdot y, і таким способом ми отримуємо всі дільники числа $x \cdot y$ x \cdot y. Отже, суму за всіма дільниками числа $x \cdot y$ x \cdot y можна подати як подвійну суму за всіма парами дільників $x_{i}$ x_i та $y_{j}$ y_j. Тоді

S_{f} (x) \cdot S_{f} (y) = i = 1 \sum k f (x_{i}) \cdot j = 1 \sum m f (y_{j}) = i, j \sum f (x_{i}) f (y_{j}) = i, j \sum f (x_{i} y_{j}) = S_{f} (x y)

S_f(x) \cdot S_f(y) = \sum_{i=1}^{k} f(x_i) \cdot \sum_{j=1}^{m} f(y_j) = \sum_{i,j} f(x_i)f(y_j) = \sum_{i,j} f(x_i y_j) = S_f(xy)

Наслідок. Розглянемо функцію $f (n) = НСД (n, c)$ f(n) = НСД(n, c), де $c$ — константа. Покажемо, що ця функція є мультиплікативною.

Якщо $x$ і $y$ взаємно прості, то

f (x \cdot y) = НСД (x \cdot y, c) = НСД (x, c) \cdot НСД (y, c) = f (x) \cdot f (y)

f(x \cdot y) = НСД(x \cdot y, c) = НСД(x, c) \cdot НСД(y, c) = f(x) \cdot f(y)

Отже функція $f (n) = НСД (n, c)$ f(n) = НСД(n, c) є мультиплікативною.

Приклад. Обчислимо $НСД (36, 90)$ використовуючи властивість мультиплікативності.

НСД (36, 90) = НСД (4 \cdot 9, 90) = НСД (4, 90) \cdot НСД (9, 90) = 2 \cdot 9 = 18

НСД(36, 90) = НСД(4 \cdot 9, 90) = НСД(4, 90) \cdot НСД(9, 90) = 2 \cdot 9 = 18

Тепер розглянемо її сумарну функцію:

g (n) = i = 1 \sum n g cd (i, n)

g(n) = \sum_{i=1}^{n} \gcd(i,n)

Із попередньої теореми ми знаємо, що сумарна функція мультиплікативної функції також є мультиплікативною. Отже, функція $g (n)$ теж мультиплікативна.

Якщо розкласти $n$ на степені простих чисел $n = p_{1}^{a_{1}} p_{2}^{a_{2}} ... p_{k}^{a_{k}}$ n = p_1^{a_1} p_2^{a_2}...p_k^{a_k}, то

g (n) = g (p_{1}^{a_{1}} p_{2}^{a_{2}} ... p_{k}^{a_{k}}) = g (p_{1}^{a_{1}}) \cdot g (p_{2}^{a_{2}}) \cdot ... \cdot g (p_{k}^{a_{k}})

g(n) = g(p_1^{a_1} p_2^{a_2}...p_k^{a_k}) = g(p_1^{a_1}) \cdot g(p_2^{a_2}) \cdot ... \cdot g(p_k^{a_k})

Лема. Нехай $d$ — дільник числа $n$ . Тоді існує рівно $φ (n / d)$ таких чисел $i$ , що $1 \leq i \leq n$ 1 \le i \le n і $НСД (i, n) = d$ НСД(i, n) = d.

► Якщо $НСД (i, n) = d$ НСД(i, n) = d, то $d$ ділить $i$ . Подамо число $i$ у вигляді $i = d \cdot j$ i = d \cdot j. Оскільки $d$ ділить $n$ , число $n$ можна записати у вигляді $n = d \cdot (n / d)$ n = d \cdot (n / d). Тоді:

НСД (i, n) = НСД (d \cdot j, n) = НСД (d \cdot j, d \cdot (n / d)) = d \cdot НСД (j, n / d)

НСД(i, n) = НСД(d \cdot j, n) = НСД(d \cdot j, d \cdot (n / d)) = d \cdot НСД(j, n / d)

Нас цікавлять такі $i$ , для яких $НСД (i, n) = d$ НСД(i, n) = d. Тому повинно виконуватися $d \cdot НСД (j, n / d) = d$ d \cdot НСД(j, n / d) = d. Звідси

НСД (j, n / d) = 1

НСД(j, n / d) = 1

Кількість чисел $j$ , взаємно простих з $n / d$ , дорівнює $φ (n / d)$ .

Приклад. Розглянемо число $n = 24$ n = 24 і знайдемо всі числа $i$ , для яких $НСД (i, 24) = 3$ НСД(i, 24) = 3. За лемою кількість таких чисел дорівнює $φ (24/3) = φ (8) = 4$ φ(24 / 3) = φ(8) = 4.

Щоб знайти ці числа, подамо $i = 3 \cdot j$ i = 3 \cdot j. Тоді з доведення леми випливає, що повинно виконуватися $НСД (j, 8) = 1$ НСД(j, 8) = 1. Рівність має місце при $j \in {1, 3, 5, 7}$ j \in \{1, 3, 5, 7\}. Отже, $НСД (i, 24) = 3$ НСД(i, 24) = 3 for $i \in {3, 9, 15, 21}$ i \in \{3, 9, 15, 21\}.

Теорема.

g (n) = i = 1 \sum n g cd (i, n) = n d ∣ n \sum \frac{φ ( d )}{d}

g(n) = \sum_{i=1}^{n} \gcd(i,n) = n \sum_{d \mid n} \frac{\varphi(d)}{d}

► Розглянемо всі числа $i$ від $1$ до $n$ і згрупуємо їх залежно від значення $НСД (i, n)$ НСД(i, n).

Нехай $НСД (i, n) = e$ НСД(i, n) = e. Згідно з наведеною вище лемою, кількість таких чисел $i$ точно дорівнює $φ (n / e)$ . Кожне таке число $i$ дає в суму $g (n)$ один і той самий внесок, що дорівнює $e$ . Тому всі числа $i$ , для яких $НСД (i, n) = e$ НСД(i, n) = e, разом дають внесок $e \cdot φ (n / e)$ e \cdot φ(n / e).

Значення $e$ завжди є дільником числа $n$ . Тому, щоб отримати всю суму $g (n)$ , потрібно підсумувати ці внески за всіма дільниками $e$ числа $n$ :

g (n) = e ∣ n \sum e φ (\frac{n}{e})

g(n) = \sum_{e \mid n} e \varphi\left(\frac{n}{e}\right)

Зробимо заміну змінної: $d = n / e$ d = n / e. Тоді $e = n / d$ e = n / d. Оскільки $e$ є дільником $n$ , число $d$ також є дільником $n$ . Підставляючи $e = n / d$ e = n / d в отриману формулу, отримуємо:

g (n) = e ∣ n \sum e φ (\frac{n}{e}) = d ∣ n \sum \frac{n}{d} φ (d) = n d ∣ n \sum \frac{φ ( d )}{d}

g(n) = \sum_{e \mid n} e \varphi\left(\frac{n}{e}\right) = \sum_{d \mid n} \frac{n}{d}\varphi(d) = n \sum_{d \mid n} \frac{\varphi(d)}{d}

Теорема. Нехай

g (n) = i = 1 \sum n g cd (i, n)

g(n) = \sum_{i=1}^{n} \gcd(i,n)

Тоді для будь-якого простого $p$ і натурального $a$ має місце співвідношення:

g (p^{a}) = (a + 1) p^{a} - a p^{a -1}

g(p^a) = (a + 1)p^a - ap^{a–1}

► При $a = 1$ a = 1 маємо:

g (p) = НСД (1, p) + НСД (2, p) + ... + НСД (p, p) = (p - 1) + p = 2 p - 1

g(p) = НСД(1, p) + НСД(2, p) + ... + НСД(p, p) = (p - 1) + p = 2p - 1

При $a = 2$ a = 2, маємо:

= (1 + 1 + \dots + 1 + p) + (1 + 1 + \dots + 1 + p) + ... (1 + 1 + \dots + 1 + p^{2}) =

= (1 + 1 + … + 1 + p) + \\ (1 + 1 + … + 1 + p) + \\ ... \\ (1 + 1 + … + 1 + p^2) =

= (p - 1 + p) \cdot (p - 1) + (p - 1 + p^{2}) = (2 p - 1) \cdot (p - 1) + (p^{2} + p - 1) = 2 p^{2} - 2 p - p + 1 + (p^{2} + p - 1) = = 3 p^{2} - 2 p

= (p - 1 + p) \cdot (p - 1) + (p - 1 + p^2) = \\ (2p - 1) \cdot (p - 1) + (p^2 + p - 1) = \\ 2p^2 - 2p - p + 1 + (p^2 + p - 1) = \\ = 3p^2 - 2p

Обчислимо $g (p^{a})$ g(p^a). Значення $НСД (i, p^{a})$ НСД(i, p^a) може бути тільки дільником числа $p^{a}$ p^a. Оскільки $p$ — просте число, всі дільники $p^{a}$ p^a мають вигляд $p^{k}$ p^k, де $0 \leq k \leq a$ 0 \le k \le a.

Знайдемо кількість чисел $i$ від $1$ до $p^{a}$ p^a, для яких $НСД (i, p^{a}) = p^{k}$ НСД(i, p^a) = p^k. Згідно з наведеною вище лемою, ця кількість дорівнює

φ (p^{a - k}) = p^{a - k} - p^{a - k - 1} (формула справедлива для a k)

φ(p^{a - k}) = p^{a - k} - p^{a - k - 1} (формула~справедлива~для~a \> k)

Крім того, для $i = p^{a}$ i = p^a маємо: $НСД (i, p^{a}) = НСД (p^{a}, p^{a}) = p^{a}$ НСД(i, p^a) = НСД(p^a, p^a) = p^a.

Тому

g (p^{a}) = k = 0 \sum a - 1 p^{k} φ (p^{a - k}) + p^{a} = k = 0 \sum a - 1 p^{k} (p^{a - k} - p^{a - k - 1}) + p^{a} = k = 0 \sum a - 1 (p^{a} - p^{a - 1}) + p^{a} = a (p^{a} - p^{a - 1}) + p^{a} = (a + 1) p^{a} - a p^{a - 1}

g(p^a) = \sum_{k=0}^{a-1} p^k \varphi\left(p^{a-k}\right) + p^a = \sum_{k=0}^{a-1} p^k \left(p^{a-k} - p^{a-k-1}\right) + p^a \\ = \sum_{k=0}^{a-1} \left(p^a - p^{a-1}\right) + p^a = a\left(p^a - p^{a-1}\right) + p^a = (a+1)p^a - ap^{a-1}

Приклад. Нехай $n = 6$ n = 6.

Тоді

g (6) = i = 1 \sum 6 g cd (i, 6) = = НСД (1, 6) + НСД (2, 6) + НСД (3, 6) + НСД (4, 6) + НСД (5, 6) + НСД (6, 6) = = 1 + 2 + 3 + 2 + 1 + 6 = 15

g(6) = \sum_{i=1}^{6} \gcd(i,6) = \\ = НСД(1, 6) + НСД(2, 6) + НСД(3, 6) + НСД(4, 6) + НСД(5, 6) + НСД(6, 6) = \\ = 1 + 2 + 3 + 2 + 1 + 6 = 15

Водночас

g (6) = g (2) \cdot g (3) = (НСД (1, 2) + НСД (2, 2)) \cdot (НСД (1, 3) + НСД (2, 3) + НСД (3, 3)) = (1 + 2) \cdot (1 + 1 + 3) = 3 \cdot 5 = 15

g(6) = g(2) \cdot g(3) = \\ (НСД(1, 2) + НСД(2, 2)) \cdot (НСД(1, 3) + НСД(2, 3) + НСД(3, 3)) = \\ (1 + 2) \cdot (1 + 1 + 3) = 3 \cdot 5 = 15

Обчислимо $g (6)$ за формулою $g (n) = n \sum_{d ∣ n} \frac{φ ( d )}{d}$ g(n) = n \sum_{d \mid n} \frac{\varphi(d)}{d}

g (6) = 6 d ∣ 6 \sum \frac{φ ( d )}{d} = 6 \cdot (\frac{φ ( 1 )}{1} + \frac{φ ( 2 )}{2} + \frac{φ ( 3 )}{3} + \frac{φ ( 6 )}{6}) = 6 φ (1) + 3 φ (2) + 2 φ (3) + φ (6) = 6 + 3 + 4 + 2 = 15

g(6) = 6 \sum_{d \mid 6} \frac{\varphi(d)}{d} = 6 \cdot \left(\frac{\varphi(1)}{1}+ \frac{\varphi(2)}{2} + \frac{\varphi(3)}{3} + \frac{\varphi(6)}{6} \right) \\ = 6\varphi(1) + 3\varphi(2) + 2\varphi(3) + \varphi(6) = 6 + 3 + 4 + 2 = 15

Обчислимо $g (6)$ виходячи з мультиплікативності функції $f (x) = НСД (x, n)$ f(x) = НСД(x, n):

g (6) = g (2) \cdot g (3) = (2 \cdot 2 - 1) \cdot (2 \cdot 3 - 1) = 3 \cdot 5 = 15

g(6) = g(2) \cdot g(3) = (2 \cdot 2 - 1) \cdot (2 \cdot 3 - 1) = 3 \cdot 5 = 15

Приклад. Нехай $n = 12$ n = 12.

Тоді

g (12) = i = 1 \sum 12 g cd (i, 12) = 1 + 2 + 3 + 4 + 1 + 6 + 1 + 4 + 3 + 2 + 1 + 12 = 40

g(12) = \sum_{i=1}^{12} \gcd(i,12) = 1 + 2 + 3 + 4 + 1 + 6 + 1 + 4 + 3 + 2 + 1 + 12 = 40

Водночас

g (12) = g (4) \cdot g (3) = (НСД (1, 4) + НСД (2, 4) + НСД (3, 4) + НСД (4, 4)) \cdot (НСД (1, 3) + НСД (2, 3) + НСД (3, 3)) = (1 + 2 + 1 + 4) \cdot (1 + 1 + 3) = 8 \cdot 5 = 40

g(12) = g(4) \cdot g(3) = \\ (НСД(1, 4) + НСД(2, 4) + НСД(3, 4) + НСД(4, 4)) \cdot \\ (НСД(1, 3) + НСД(2, 3) + НСД(3, 3)) = \\ (1 + 2 + 1 + 4) \cdot (1 + 1 + 3) = 8 \cdot 5 = 40

Обчислимо $g (12)$ за формулою $g (n) = n \sum_{d ∣ n} \frac{φ ( d )}{d}$ g(n) = n \sum_{d \mid n} \frac{\varphi(d)}{d}:

g (12) = 12 d ∣ 12 \sum \frac{φ ( d )}{d} = 12 \cdot (\frac{φ ( 1 )}{1} + \frac{φ ( 2 )}{2} + \frac{φ ( 3 )}{3} + \frac{φ ( 4 )}{4} + \frac{φ ( 6 )}{6} + \frac{φ ( 12 )}{12}) = 12 φ (1) + 6 φ (2) + 4 φ (3) + 3 φ (4) + 2 φ (6) + φ (12) = 12 + 6 + 8 + 6 + 4 + 4 = 40

g(12) = 12 \sum_{d \mid 12} \frac{\varphi(d)}{d} = 12 \cdot \left( \frac{\varphi(1)}{1} + \frac{\varphi(2)}{2} + \frac{\varphi(3)}{3} + \frac{\varphi(4)}{4} + \frac{\varphi(6)}{6} + \frac{\varphi(12)}{12} \right) \\ = 12\varphi(1) + 6\varphi(2) + 4\varphi(3) + 3\varphi(4) + 2\varphi(6) + \varphi(12) \\ = 12 + 6 + 8 + 6 + 4 + 4 = 40

Дільниками числа $12$ є: $1, 2, 3, 4, 6, 12$ 1, 2, 3, 4, 6, 12. Кількість таких $i$ що $НСД (i, 12) = d$ НСД(i, 12) = d дорівнює $ϕ (12/ d)$ . Наприклад $НСД (i, 12) = 3$ НСД(i, 12) = 3 має місце для $ϕ (12/3) = ϕ (4) = 2$ ϕ(12/3) = ϕ(4) = 2 різних $i$ , а саме для $i = 3, 9$ i = 3, 9.

Обчислимо $g (12)$ виходячи з мультиплікативності функції $f (x) = НСД (x, n)$ f(x) = НСД(x, n):

g (12) = g (2^{2}) \cdot g (3) = (3 \cdot 2^{2} - 2 \cdot 2) \cdot (2 \cdot 3 - 1) = 8 \cdot 5 = 40

g(12) = g(2^2) \cdot g(3) = (3 \cdot 2^2 - 2 \cdot 2) \cdot (2 \cdot 3 - 1) = 8 \cdot 5 = 40

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

Функція euler обчислює функцію Ейлера.

long long euler(long long n)
{
  long long i, result = n;
  for (i = 2; i * i <= n;i++)
  {
    if (n % i == 0) result -= result / i;
    while (n % i == 0) n /= i;
  }
  if (n > 1) result -= result / n;
  return result;
}

C++

Основна частина програми. Читаємо значення $n$ . Обчислимо значення $g (n)$ за формулою $\sum_{e ∣ n} e φ (\frac{n}{e})$ \sum_{e \mid n} e \varphi\left(\frac{n}{e}\right). Всі дільники числа $n$ шукаємо серед чисел від $1$ до $⌊ n ⌋$ \lfloor \sqrt{n} \rfloor.

Якщо $i$ є дільником $n$ , то число $n / i$ також є дільником $n$ . Тому при знаходженні кожного дільника $i \leq ⌊ n ⌋$ i \le \lfloor \sqrt{n} \rfloor, до результату $r es$ слід додати $i ϕ (\frac{n}{i}) + \frac{n}{i} ϕ (i)$ i \phi(\frac{n}{i}) + \frac{n}{i} \phi(i), що враховує обидва дільники $i$ і $n / i$ .

Якщо $n$ є повним квадратом і $i = s q = ⌊ n ⌋$ i = sq = \left\lfloor \sqrt{n} \right\rfloor, то дільники $i$ і $n / i$ збігаються. У цьому випадку $i ϕ (\frac{n}{i}) = \frac{n}{i} ϕ (i)$ iϕ(\frac{n}{i}) = \frac{n}{i} ϕ(i) і в суму $r es$ додадуться два однакових доданки. Тому один з них віднімаємо від $r es$ вже на етапі ініціалізації цієї змінної.

while(scanf("%lld",&n) == 1)
{
  sq = (long long)sqrt(1.0*n);
  res = (sq * sq == n) ? -sq * euler(sq) : 0;

  for (i = 1; i <= sq; i++)
    if(n % i == 0) res = res + i * euler(n/i) + (n / i) * euler(i);
  printf("%lld\n",res);
}

C++

Реалізація алгоритму – з використанням мультиплікативності

Розкладемо число $n$ на прості множники:

n = p_{1}^{a_{1}} p_{2}^{a_{2}} ... p_{k}^{a_{k}}

n = p_1^{a_1} p_2^{a_2} ... p_k^{a_k}

Ми довели, що функція $g (n) = \sum_{i = 1}^{n} g cd (i, n)$ g(n) = \sum_{i=1}^{n} \gcd(i,n) мультиплікативна. Тому

g (n) = g (p_{1}^{a_{1}}) \cdot g (p_{2}^{a_{2}}) \cdot \dots \cdot g (p_{k}^{a_{k}})

g(n) = g(p_1^{a_1}) \cdot g(p_2^{a_2}) \cdot \ldots \cdot g(p_k^{a_k})

А для степеня простого числа ми довели формулу:

g (p^{a}) = (a + 1) p^{a} - a p^{a - 1}

g(p^a) = (a + 1)p^a - ap^{a-1}

Саме ці дві формули безпосередньо використовуються в програмі.

Обробляємо декілька тестів. Читаємо значення $n$ .

while(scanf("%lld",&n) == 1)
{

У змінній $r es$ будемо обчислювати значення $g (n)$ .

  res = 1;

Розкладаємо на прості множники число $n$ . Перебираємо дільники.

  for (i = 2; i * i <= n; i++)
  {

Якщо число $i$ просте, то виокремлюємо множник $p = i^{a}$ p = i^a.

    if (n % i == 0)
    {
      a = 0; p = 1;
      while(n % i == 0)
      {
        a++;
        p *= i;
        n /= i;
      }

C++

Множимо результат $r es$ на

g (p) = g (i^{a}) = (a + 1) \cdot i^{a} - a \cdot i^{a - 1} = (a + 1) \cdot p - a \cdot p / i

g(p) = g(i^a) = (a + 1) \cdot i^a - a \cdot i^{a - 1} = (a + 1) \cdot p - a \cdot p / i

      res *= (a + 1) * p - a * p / i;
    }
  }

Якщо $n > 1$ n > 1, то $n$ останній простий множник.

  if (n > 1) res *= (2*n - 1);

Виводимо відповідь.

  printf("%lld\n",res);
}

Java реалізація

import java.util.Scanner;

public class Main
{
  static long euler(long n)
  {
    long result = n;
    for(int i = 2; i <= Math.sqrt(n);i++)
    {
      if (n % i == 0) result -= result / i;
      while (n % i == 0) n /= i;
    }
    if (n > 1) result -= result / n;
    return result;
  }
    
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    while(con.hasNext())
    {
      long n = con.nextLong();
      long sq = (long)Math.sqrt(n);
      long res = (sq * sq == n) ? -sq * euler(sq) : 0;
      for(long i = 1; i <= sq; i++)
        if (n % i == 0)
          res = res + i * euler(n/i) + (n / i) * euler(i);
      System.out.println(res);
    }
    con.close();
  }
}

Java