MAXimal | |
добавлено: 10 Jun 2008 10:57 Содержание [скрыть] Функция ЭйлераОпределениеФункция Эйлера (иногда обозначаемая или ) — это количество чисел от до , взаимно простых с . Иными словами, это количество таких чисел в отрезке , наибольший общий делитель которых с равен единице. Несколько первых значений этой функции (A000010 в энциклопедии OEIS): СвойстваТри следующих простых свойства функции Эйлера — достаточны, чтобы научиться вычислять её для любых чисел:
Отсюда можно получить функцию Эйлера для любого через его факторизацию (разложение на простые сомножители): если (где все — простые), то РеализацияПростейший код, вычисляющий функцию Эйлера, факторизуя число элементарным методом за : int phi (int n) { int result = n; for (int i=2; i*i<=n; ++i) if (n % i == 0) { while (n % i == 0) n /= i; result -= result / i; } if (n > 1) result -= result / n; return result; } Ключевое место для вычисление функции Эйлера — это нахождение факторизации числа . Его можно осуществить за время, значительно меньшее : см. Эффективные алгоритмы факторизации. Приложения функции ЭйлераСамое известное и важное свойство функции Эйлера выражается в теореме Эйлера: где и взаимно просты.В частном случае, когда простое, теорема Эйлера превращается в так называемую малую теорему Ферма: Теорема Эйлера достаточно часто встречается в практических приложениях, например, см. Обратный элемент в поле по модулю. Задачи в online judgesСписок задач, в которых требуется посчитать функцию Эйлера,либо воспользоваться теоремой Эйлера, либо по значению функции Эйлера восстанавливать исходное число:
|