Функция Эйлера

Определение

Функция Эйлера, обозначаемая как $ \varphi(x)$, показывает количество чисел не больших $x$ и взаимопростых с ним.

Другими словами, $\varphi(x)$, показывает количество натуральных $y, y \le x, gcd(x, y) = 1$

Свойства

1. Для любого простого $p$, верно $\varphi(p) = p-1$, т.к. любые два числа являются взаимопростыми, если хотя бы одно из них простое (если только они не равны).

2. Для степени простого числа $\varphi(p^n) = p^n-p^{n-1} = p^{n-1}*(p-1)$

3. Также для любых двух чисел $n$ и $m$ верно следующее равенство: $$ \varphi(mn) = \varphi(n)*\varphi(m) * {gcd(n,m)\over{\varphi(gcd(n,m))}} $$

4. Легко заметить, что для взаимопростых чисел $\varphi(mn) = \varphi(n)*\varphi(m)$

5. Если рекурсивно применять функцию к какому-то значению $x$, глубина рекурсии составит около логарифма.

Вычисление

Вычислить $\varphi(x)$ за $\sqrt{x}$, путем перебора простых делителей $x$, т.к. мы разобьем число на взаимопростые делители и сможем найти их функции, как степени простых чисел, а потом перемножить, как взаимопростые.

Не менее интересным является способ предподсчета всех $\varphi(x), 1\le x\le n$.

Это можно будет делать используя свойства функции. Метод похож на вычисление простых чисел решета Эратосфена.



#define MAXN 100000
      
int f[MAXN];

for (int i=1; i < MAXN; i++)
 f[i] = i;

for(int i=2; i < MAXN; i++)
 if(f[i] == i) //Ни разу не пробегались по этому элементу => i - простое 
  {
   f[i] = i-1; // f от простого p равно p-1                     
   for(int j=2*i; j < n; j+=i)
    f[j] = (f[j]/i) * (i-1); 
    // f(j) - произведение всех p^{k-1}*(p-1), где p - простые делители j
    // а k - максимальное вхождение p в j
  }

Итого, все составные числа будут разбиты на произведение функций от простых множителей. Таким образом сложность алгоритма $O(n \log{\log{n}} )$.

Предподсчет за O(n)

Давайте предподсчитаем с помощью линейного решета все $d[i]$ - минимальный простой делитель $i$.

Теперь выведем рекуррентное нахождение $f[i]$.

Давайте возьмем $d[i]$. Если $i$ единождый делится на $d[i]$, то возьмем $f[i/d[i]]$ и домножим на $d[i]-1$, иначе домножим на $d[i]$. Так для каждого простого $p$, входящего $k$ раз в факторизация числа, мы один раз учтем $(p-1)$ и оставшиеся разы домножим на $p^{k-1}$.


for(int i=2;i<=n;i++) {
  int p = d[i];
  f[i] = f[i/p] * (p - ( (i/p)% p != 0) );
}