Леонард Эйлер швейцарский, немецкий и российский математик и механик, внёсший фундаментальный вклад в развитие этих наук, а также физики, астрономии и других. Эйлер - автор более чем 850 работ по математическому анализу, дифференциальной геометрии, теории чисел, приближённым вычислениям, небесной механике, и математической физике. Он глубоко изучал медицину, химию, ботанику, воздухоплавание, теорию музыки, множество европейских и древних языков. Решение уравнений Эйлера является весьма нетривиальной задачей и требует определенных знаний. Уравнения данного рода имеют средний уровень сложности и изучаются в старших классах школы.
Уравнение Эйлера имеет следующий вид:
\ - постоянные числа.
Благодаря замене \ данное уравнение преобразуется к уравнению с постоянными коэффициентами:
Получаем:
Подставив эти значения, мы получим уравнение с постоянными коэффициентами относительно функции \
Допустим, дано такое уравнение Эйлера:
Решение данного уравнения будем искать в виде \ поэтому:
Вставив эти значения производных получим:
\=0\]
Соответственно, если \ Поскольку \ второй кратности, то\[ y = \frac{1}{x}\] является решением уравнения Эйлера. Другое решение \. В этом можно убедиться, поскольку \[\frac {1}{x}\] и \[ \frac {(ln x)}{x}\] линейно независимые, то:
Это и есть общее решение данного вида уравнения Эйлера.
Решить уравнение вы можете на нашем сайте https://сайт. Бесплатный онлайн решатель позволит решить уравнение онлайн любой сложности за считанные секунды. Все, что вам необходимо сделать - это просто ввести свои данные в решателе. Так же вы можете посмотреть видео инструкцию и узнать, как решить уравнение на нашем сайте. А если у вас остались вопросы, то вы можете задать их в нашей групе Вконтакте http://vk.com/pocketteacher. Вступайте в нашу группу, мы всегда рады помочь вам.
Условие
В теории чисел известна функция Эйлера $latex \varphi(n)$ — количество чисел, меньших $latex n$ и взаимно простых с ним. Напомним, два числа взаимно просты, если у них нет общих делителей, кроме единицы.
Расширим понятие функции Эйлера на строки. Пусть $latex s$ — непустая строка над алфавитом {$latex a$ .. $latex z$}, а $latex k$ — целое положительное число. Тогда $latex s \cdot k$ по определению — строка $latex t = \underbrace{s \circ s \circ \ldots \circ s}_{\text{k}}$ (конкатенация $latex s$ самой с собой $latex k$ раз). В таком случае будем говорить, что строка $latex s$ — делитель строки $latex t$. Например, «ab» — делитель строки «ababab».
Две непустые строки $latex s$ и $latex t$ будем называть взаимно простыми, если не существует строки $latex u$ такой, что она — делитель и для $latex s$, и для $latex t$. Тогда функция Эйлера $latex \varphi(s)$ для строки $latex s$ по определению — количество непустых строк над тем же алфавитом {$latex a$ .. $latex z$}, меньших $latex s$ по длине, и взаимно простых с ней.
Входные данные
Во входном файле дана строка $latex s$ длиной от $latex 1$ до $latex 10^5$ символов включительно, состоящая из маленьких латинских букв.
Выходные данные
Вычислите значение $latex \varphi(s)$ и выведите единственное число — остаток от его деления на $latex 1000000007 (10^9 + 7)$.
Решение
Очевидно, что когда строка $latex s$ длины $latex n$ не имеет делителей, кроме самой себя, любая строка длины меньшей, чем $latex n$, будет взаимно простой с $latex s$. Тогда достаточно посчитать количество всех возможных строк длины от $latex 1$ до $latex n-1$ включительно. Для некоторого $latex k$ количество строк этой длины будет равно $latex 26^k$. Тогда количество $latex m$ всех возможных строк длины от $latex 1$ до $latex n-1$ будет вычисляться по следующей формуле: $latex m=\sum\limits_{k=1}^{n-1} 26^k$.
Теперь рассмотрим случай, когда строка имеет делители. Поскольку строка $latex s$ в таком случае является конкатенацией некоторого количества одинаковых строк меньшей длины, найдём эту самую подстроку, кторая является минимальным (кратчайшим) делителем строки $latex s$. Для этого воспользуемся префикс-функцией. Она возвращает вектор $latex pi$ значений для всех подстрок строки $latex s$, которые являются префиксами $latex s$, где значение — максимальная длина префикса строки, совпадающего с её суффиксом. Тогда на $latex n-1$-ом месте вектора $latex pi$ будет стоять длина наибольшего префикса строки $latex s$, а оставшийся «кусочек» строки $latex s$ будет представлять собой минимальный делитель.
Осталось вычислить количество строк, которые не взаимно просты с $latex s$. Пусть k — длина минимального делителя $latex s$. Тогда все строки, являющиеся конкатенациями этого делителя, не будут взаимно простыми с $latex s$. Для подсчёта их количества достаточно поделить длину исходной строки на k, но ответ будет на единицу меньше, поскольку в этой формуле учитывается и сама строка $latex s$, как собственный делитель.
Для окончательного ответа на задачу остаётся вычесть из общего количества строк количество не взаимно простых с $latex s$.
Тесты
| № | Входные данные | Выходные данные |
| 1 | aa | 25 |
| 2 | abab | 18277 |
| 3 | abcdefgh | 353082526 |
| 4 | aaaaaab | 321272406 |
| 5 | aaaaaaa | 321272406 |
Программный код
#include #include using namespace std ; const int MOD = 1e9 + 7 ; vector < int > prefix_function (string s ) { int n = s . length () ; vector < int > pi (n ) ; pi [ 0 ] = 0 ; for (int i = 1 ; i < n ; i ++ ) { int j = pi [ i - 1 ] ; while (j > 0 && s [ i ] != s [ j ] ) j = pi [ j - 1 ] ; if (s [ i ] == s [ j ] ) j ++ ; pi [ i ] = j ; return pi ; int main () { string s ; cin >> s ; int n = s . length () ; long long mul = 26 , ans = 0 ; for (int i = 1 ; i < n ; i ++ , mul *= 26 , mul %= MOD ) |
И значения ее лежат в множестве натуральных чисел.
Как следует из определения, чтобы вычислить нужно перебрать все числа от до и для каждого проверить, имеет ли оно общие делители с а затем подсчитать, сколько чисел оказались взаимно простыми с Эта процедура весьма трудоемка, поэтому для вычисления используют другие методы, которые основываются на специфических свойствах функции Эйлера.
В таблице справа представлены первые 99 значений функции Эйлера. Анализируя эти данные, можно заметить, что значение не превосходит , и в точности ему равно, если - простое. Таким образом, если в координатах провести прямую то значения будут лежать либо на этой прямой, либо ниже её. Также, глядя на график, приведенный в начале статьи, и на значения в таблице, можно предположить, что существует прямая, проходящая через ноль, которая ограничивает значения снизу. Однако, оказывается, такой прямой не существует. То есть, какую бы пологую прямую мы ни провели, всегда найдется натуральное число такое что лежит ниже этой прямой. Еще одной интересной особенностью графика, является наличие некоторых прямых, вдоль которых концентрируются значения функции Эйлера. Так, например, помимо прямой на которой лежат значения где - простое, выделяется прямая, примерно соответствующая на которую попадают значения где - простое.
Более подробно поведение функции Эйлера рассматривается в разделе .
| +0 | +1 | +2 | +3 | +4 | +5 | +6 | +7 | +8 | +9 | |
|---|---|---|---|---|---|---|---|---|---|---|
| 0+ | 1 | 1 | 2 | 2 | 4 | 2 | 6 | 4 | 6 | |
| 10+ | 4 | 10 | 4 | 12 | 6 | 8 | 8 | 16 | 6 | 18 |
| 20+ | 8 | 12 | 10 | 22 | 8 | 20 | 12 | 18 | 12 | 28 |
| 30+ | 8 | 30 | 16 | 20 | 16 | 24 | 12 | 36 | 18 | 24 |
| 40+ | 16 | 40 | 12 | 42 | 20 | 24 | 22 | 46 | 16 | 42 |
| 50+ | 20 | 32 | 24 | 52 | 18 | 40 | 24 | 36 | 28 | 58 |
| 60+ | 16 | 60 | 30 | 36 | 32 | 48 | 20 | 66 | 32 | 44 |
| 70+ | 24 | 70 | 24 | 72 | 36 | 40 | 36 | 60 | 24 | 78 |
| 80+ | 32 | 54 | 40 | 82 | 24 | 64 | 42 | 56 | 40 | 88 |
| 90+ | 24 | 72 | 44 | 60 | 46 | 72 | 32 | 96 | 42 | 60 |
Одним из основных свойств функции Эйлера является её мультипликативность . Это свойство было установлено еще Эйлером и формулируется оно следующим образом: для любых взаимно простых чисел и
Доказательство мультипликативности
Для доказательства мультипликативности функции Эйлера потребуется следующая вспомогательная теорема.
Теорема 1. Пусть и пробегает приведенную систему вычетов по модулю в то время как пробегает приведенную систему вычетов по модулю Тогда пробегает приведенную систему вычетов по модулю Доказательство. Если тогда поэтому аналогично Поэтому существует несравнимых по модулю чисел, которые образуют приведенную систему вычетов по модулюТеперь можно доказать основное утверждение.
Теорема 2. Функция Эйлера мультипликативна. Доказательство. Если то по Теореме 1 пробегает приведенную систему вычетов по модулю когда и пробегают приведенные системы вычетов по модулям и соответственно. Также: Поэтому чисел, которые меньше числа и взаимно просты с ним, являются наименьшими положительными вычетами среди значений для которых взаимно просто с и взаимно просто с Отсюда следует, чтокоторая следует из определения. Действительно, если - простое, то все числа, меньшие , взаимно просты с ним, а их ровно штук.
Для вычисления функции Эйлера от степени простого числа используют следующую формулу:
Это равенство обосновывается следующим образом. Подсчитаем количество чисел от до , которые не взаимно просты с . Все они, очевидно, кратны то есть, имеют вид: Всего таких чисел Поэтому количество чисел, взаимно простых с равно
Вычисление для произвольного натурального основывается на мультипликативности функции Эйлера, выражении для а также на основной теореме арифметики . Для произвольного натурального числа значение представляется в виде:
где - простое число и пробегает все значения, участвующие в разложении на простые сомножители.
Доказательство
где - наибольший общий делитель и Это свойство является естественным обобщением мультипликативности.
Доказательство обобщённой мультипликативности
Пусть тогда причем в общем случае и Поэтому можно записать:
Здесь первые делителей являются также делителями а последние делителей являются делителями Распишем:
В силу мультипликативности функции Эйлера, а также с учетом формулы
где - простое, получаем:
В первой строке записано во второй - а третью можно представить, как Поэтому:
Некоторые частные случаи:
Наиболее часто на практике используется свойство, установленное Эйлером :
если и взаимно просты .
Это свойство, которое называют теоремой Эйлера , вытекает из Теоремы Лагранжа и того факта, что φ(m
) равна порядку группы обратимых элементов кольца вычетов по модулю m
.
В качестве следствия теоремы Эйлера можно получить малую теорему Ферма . Для этого нужно взять не произвольное а простое. Тогда:
Последняя формула находит применение в различных тестах простоты .
Исходя из представимости произведением Эйлера, несложно получить следующее полезное утверждение:
Всякое натуральное число представимо в виде суммы значений функции Эйлера от его делителей:
Сумма всех чисел, меньших данного, и взаимно простых с ним, выражается через функцию Эйлера:
Исследование структуры множества значений функции Эйлера является отдельной сложной задачей. Здесь представлены лишь некоторые результаты, полученные в этой области.
Доказательство (функция Эйлера принимает только чётные значения при n > 2)
Действительно, если - простое нечётное и то - чётное. Из равенства следует утверждение.
В действительном анализе часто возникает задача нахождения значения аргумента по заданному значению функции, или, другими словами, задача нахождения обратной функции . Подобную задачу можно поставить и для функции Эйлера. Однако, надо иметь в виду, что
В связи с этим нужны особые методы анализа. Полезным инструментом для исследования прообраза является следующая теорема:
Если тоДоказательство теоремы
Очевидно, если то С другой стороны, если и то Однако, если то Поэтому Следовательно
Эта теорема показывает, что прообраз элемента всегда представляет собой конечное множество. Также она дает практический способ нахождения прообраза. Для этого нужно
Может оказаться, что в указанном промежутке нет такого числа что в этом случае прообраз является пустым множеством .
Стоит отметить, что для вычисления нужно знать разложение на простые сомножители, что для больших является вычислительно сложной задачей. Затем, нужно раз вычислить функцию Эйлера, что для больших чисел также весьма трудоёмко. Поэтому нахождение прообраза в целом является вычислительно сложной задачей.
Пример 1 (Вычисление прообраза)
Найдем прообраз 4. Делителями 4 являются числа 1, 2 и 4. Добавляя по единице к каждому из них, получаем 2, 3, 5 - простые числа. Вычисляем
Чтобы найти прообраз 4, достаточно рассмотреть числа от 5 до 15. Проделав выкладки, получим:
Пример 2 (Не все чётные числа являются значениями функции Эйлера)
Не существует, например, такого числа что То есть:
В самом деле, делители 14 суть 1, 2, 7 и 14. Добавив по единице, получим 2, 3, 8, 15. Из них только первые два числа - простые. Поэтому
Перебрав все числа от 15 до 42, несложно убедиться, что
На основе алгоритма, предложенного в 1978 году Рональдом Ривестом , Ади Шамиром и Леонардом Адлеманом была построена первая система шифрования с открытым ключом, получившая название по первым буквам фамилий авторов - система RSA . Криптостойкость этой системы определяется сложностью разложения на сомножители целого n -разрядного числа. Ключевую роль в алгоритме RSA играет функция Эйлера, свойства которой и позволяют построить криптографическую систему с открытым ключом .
На этапе создания пары из секретного и открытого ключей, вычисляется
где и - простые. Затем выбираются случайные числа так, чтобы
Затем сообщение шифруется открытым ключом адресата:
После этого расшифровать сообщение может только обладатель секретного ключа
Корректность последнего утверждения основывается на теореме Эйлера и китайской теореме об остатках .
Доказательство корректности расшифрования
В силу выбора чисел на этапе создания ключей
Если то, с учетом теоремы Эйлера,
В общем случае и могут иметь общие делители, но расшифрование все равно оказывается верным. Пусть По китайской теореме об остатках:
Подставляя получаем тождество
Следовательно,
Функция Эйлера может быть использована для вычисления обратного по умножению элемента по модулю , а именно:
еслиПример (Вычисление обратного элемента)
Найдем , то есть такое число , что
Очевидно, и не имеют общих делителей кроме единицы, , при этом число простое и
поэтому удобно воспользоваться формулой, приведенной выше:
Легко проверить, что в самом деле
Замечание 1 (Оценка сложности вычисления)
В общем случае для вычисления обратных значений алгоритм Эвклида быстрее, чем использование теоремы Эйлера, так как битовая сложность вычисления по алгоритму Эвклида имеет порядок в то время как вычисление по теореме Эйлера требует порядка битовых операций, где Однако, в случае, когда известно разложение на простые сомножители, сложность вычислений можно уменьшить, используя алгоритмы быстрого возведения в степень: Алгоритм Монтгомери или алгоритм "возводи в квадрат и перемножай" .
Замечание 2 (Отсутствие решения в случае (a, n) ≠ 1)
Если то обратного к элемента не существует, или, иначе говоря, уравнение
не имеет решения на множестве натуральных чисел.
Доказательство.
В самом деле, допустим
и решение существует. Тогда по определению наибольшего общего делителя
причемпоэтому можно записать:
гдеили, перегруппировав слагаемые,
Слева стоит целое отличное от нуля число, значит и справа должно быть целое отличное от нуля число, поэтому с необходимостью
что противоречит предположению.
Метод вычисления обратного элемента можно использовать для решения сравнения
еслиПример (Решение линейного сравнения)
Рассмотрим сравнение
Так как можно воспользоваться указанной формулой:
Подстановкой убеждаемся, что
Замечание (Неединственность решения или отсутствие решения в случае (a, n) ≠ 1)
Если , сравнение либо имеет не единственное решение, либо не имеет решения. Как легко убедиться, сравнение
не имеет решения на множестве натуральных чисел. В то же время сравнение
имеет два решения
Функции Эйлера позволяет вычислять остатки от деления больших чисел.
Пример 1 (Последние три цифры в десятичной записи числа)
Найдем последние три цифры в десятичной записи числа Замечая, что
получаем
Переходя теперь от модуля к модулю имеем:
Следовательно, десятичная запись числа оканчивается на
Пример 2 (Остаток от деления на 1001)
Найдем остаток от деления на Легко видеть, что
Поэтому, воспользовавшись мультипликативностью функции Эйлера и равенством
для всякого простогополучаем
Мультипликативная группа кольца вычетов по модулю состоит из классов вычетов .
Пример.
Приведённая система вычетов по модулю 14 состоит из классов вычетов:
Число порождающих элементов в конечной циклической группе равно . В частности, если мультипликативная группа кольца вычетов по модулю является циклической группой - что возможно только при , где - простое нечетное, - натуральное, - то существует генераторов группы (первообразных корней по модулю ).
Пример.
Группа рассмотренная в примере выше, имеет генератора: и
Как известно, если - простое, то В 1932 Лемер (англ. ) задался вопросом, существует ли такое составное число что является делителем Лемер рассматривал уравнение
где - целое. Ему удалось доказать, что если - решение уравнения, то либо - простое, либо оно является произведением семи или более различных простых чисел. Позже были доказаны и другие сильные утверждения. Так в 1980 году Cohen и Hagis показали, что если составное и делит то и где - количество простых делителей. В 1970 году Lieuwens установил, что если то и Wall в 1980 году доказал, что если то
Функция Эйлера (n) определяется для всех целых положительных n и представляет собою число чисел ряда
0,1,…n-1(2.1.)
взаимно простых с n
Теорема2.1. пусть n=…(2.2.)
Каноническое разложение числа n, тогда имеем
или также
(n)n=(-) (-)…(-) (2.4.)
в частности будем иметь
(p 2)= p 2 - p -1 , (p)=p-1 (2.5.)
Действительно, применим теорему 1.8. При этом числа?, f определим так: пусть x пробегают числа ряда (2.1) каждому значению x приведен в соответствие число? =(x, n) и числа x=1.
Тогда S / обратится в число значений =(x, n), равных 1 , т.е. в (n). А S d
Обратится в число значений =(x, n) кратных d.
Но (x,n) может быть кратным d, лишь при условии, что d -делитель числа n .При наличии этого условия S d обратится в число значений x, кратных d, т.е. в.
Откуда ввиду (***) следует формула (2.3.), а из последней в виду (2.2.)
Следует формула (2.4.)
Мультипликативность функции Эйлера и ее связь с другими мультипликативными Функциями.
Теорема 2.2. (n) - мультипликативна, т.е.
(n 1 n 2) = (n 1)(n 2), при (n 1 ,n 2) = 1
Дадим два доказательства этой теореме:
1. Пусть x приобретает значение 1, 2,…, (n2), образующие приведенную систему вычетов по модулю n2, а y приобретает значения S1, S2,…, S(n1), образующие приведенную систему вычетов по n1 модулю. Составим всевозможные числа вида n11 +n2sj, соответствующие размещенным парам j sj, число таких чисел будет равна
С другой стороны поскольку (n 1 ,n 2) = 1 , эти числа образуют приведенную систему вычетов по модулю n 1 n 2 , т.е. число таких чисел должно равняться (n 1 n 2).Произведение (n 1) (n 2) и (n 1 n 2) выражают одну и ту же величину, т.е.
(n 1 n 2)= (n 1) (n 2)
n 2 +1,n 2 +2,n 2 +3,…, 2 n 2
2n 2 +1,2n 2 +2,2n 2 +3,…, 3 n 2 (2.7)
…………………………………………
(n 1 -1) n 2 +1, (n 1 -1) n 2 +2, (n 1 -1) n 2 +3,…, n 1 n 2
и определим число чисел в этой таблице, взаимно простых с n 1 n 2
(kn 2 +, n 2)=1,
тогда и только тогда, когда (, n 2)=1
Таким образом, числа взаимно простые с n 2 , а тем более с n 1 n 2 могут быть только в столбцах номерами, такими что (, n 2)=1, где 1 n 2 число таких столбцов по определению равно (n 2).
Каждый такой столбец состоит из чисел:
N 2 +, 2n 2 +,…, (n 1 -1) n 2 + (2.8.)
т.е. из чисел вида n 2 x+, где пробегает полную систему вычетов по модулю n. Поскольку (n 1 n 2)=1, то числа (2.8.) образуют также полную систему вычетов по модулю n. И следовательно в (2.8.) содержится (n 1) чисел, взаимно простых с n 2 . Мы имеем таким образом, в таблице (2.7.) (n 2) столбцов чисел, взаимно простых с n 2 , причем каждый такой столбец содержит (n 1) чисел, взаимно простых с n 1 . Если число взаимно с n 2 и с n 1 , то оно взаимно просто с n 1 n 2 . Таким образом, таблица (2.7.) содержит (n 1) (n 2) чисел, взаимно простых с n 1 n 2 .
С другой стороны эта таблица содержит все числа от 1 до n 1 n 2 и таким образом в ней (n 1 n 2) чисел, взаимно простых с n 1 n 2 , т.е.
(n 1) (n 2)= (n 1 n 2)
Теорема 2.3. При n1 (n)=n
Знак p означает здесь то, что множители произведения берутся при всевозможных простых делителях числа n. Доказательство: Любое n1
можно представить в канонической форме
