Функция Эйлера (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)

• 2. Составим таблицу:
• 1,2,3,…,

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

можно представить в канонической форме

Леонард Эйлер швейцарский, немецкий и российский математик и механик, внёсший фундаментальный вклад в развитие этих наук, а также физики, астрономии и других. Эйлер - автор более чем 850 работ по математическому анализу, дифференциальной геометрии, теории чисел, приближённым вычислениям, небесной механике, и математической физике. Он глубоко изучал медицину, химию, ботанику, воздухоплавание, теорию музыки, множество европейских и древних языков. Решение уравнений Эйлера является весьма нетривиальной задачей и требует определенных знаний. Уравнения данного рода имеют средний уровень сложности и изучаются в старших классах школы.

Уравнение Эйлера имеет следующий вид:

\ - постоянные числа.

Благодаря замене \ данное уравнение преобразуется к уравнению с постоянными коэффициентами:

Получаем:

Подставив эти значения, мы получим уравнение с постоянными коэффициентами относительно функции \

Допустим, дано такое уравнение Эйлера:

Решение данного уравнения будем искать в виде \ поэтому:

Вставив эти значения производных получим:

\=0\]

Соответственно, если \ Поскольку \ второй кратности, то\[ y = \frac{1}{x}\] является решением уравнения Эйлера. Другое решение \. В этом можно убедиться, поскольку \[\frac {1}{x}\] и \[ \frac {(ln x)}{x}\] линейно независимые, то:

Это и есть общее решение данного вида уравнения Эйлера.

Где можно решить уравнение Эйлера онлайн?

Решить уравнение вы можете на нашем сайте https://сайт. Бесплатный онлайн решатель позволит решить уравнение онлайн любой сложности за считанные секунды. Все, что вам необходимо сделать - это просто ввести свои данные в решателе. Так же вы можете посмотреть видео инструкцию и узнать, как решить уравнение на нашем сайте. А если у вас остались вопросы, то вы можете задать их в нашей групе Вконтакте http://vk.com/pocketteacher. Вступайте в нашу группу, мы всегда рады помочь вам.

Числовые функции

В теории чисел есть ряд числовых функций зависящих от натуральных чисел. Мы рассмотрим часть этих функций, которые находят широкое применение как в криптоалгоритмах так и в криптоанализе.

Имеется целое, положительное число m. Оно может быть как составным, так и простым.

Функцию Эйлера принято обозначать, практически во всех учебниках как:

Назначение функции:

Допустим, мы имеем число m – натуральное. Рассмотрим на оси все числа.

1,2,3,4…. m-1 m

Сколько чисел в диапазоне от 1 до m-1 (m) , являются взаимно простыми? (имеют с m НОД=1)

(a,m)=1 – должны быть взаимно простыми. (должны быть взаимно простыми с m)

Если m=p, то взаимно простых будет p-1. Т.к. если число m-простое, то все числа являются для него взаимно простыми, исключая само число m.

Ну а если число m составное?

Эйлер установил такую закономерность, что существует определенная формула, по которой можно вычислить число взаимно простых. (самый простой способ это перебор).

Эта формула определяется на основе разложения числа m.

Раскладываем на простые сомножители.

Теперь надо использовать только различающиеся сомножители. Пример:

m= 60 = 2*2*3*5; в каноническом виде - 2 2 *3*5: p 1 =2; p 2 =3; p 3 =5;

Справка: Любое составное число раскладывается однозначно.

Есть формула которая учитывает кратность сомножителей, а некоторые не учитывают.

Если все сомножители разные, то это одна формула, а если каноническая, то можно выразить ее через показатели.

Эти две формулы мы и рассмотрим.

Пусть разложение такого, что все сомножители разные.

I) Участвует само число m, затем следует рекуррентное выражение:

В нашем случае:

Значит, от 1 до 60 находятся 16 взаимно простых чисел с 60.

В нашем случае:

Отметим приложение в криптографии.

В криптографии часто надо вычислять, шифровать по некоторому модулю. Модуль может быть как составным так и простым. Когда модуль составное число, тогда и используется функция Эйлера для однозначного шифрования. Там осуществляется работа с множеством чисел, которые являются взаимно простыми в заданном модулем диапазоне.

Классическое (наиважнейшее) приложение этой функции такое :

Заданно некоторое натуральное число a и заданно некоторое число m, пусть m-составное, натуральное, положительное. Если эти два числа взаимно просты, тогда для этой пары чисел справедлива следующая теорема (теорема Эйлера ) :

Берем число a, возводим в ,берем модуль от

т.е. остаток будет равен всегда единице.

Это мы рассматривали нахождением обратных элементов. К этой теореме мы вернемся позже.

Частный случай: m- простое(p), то:

Это теорема малая Ферма, а Эйлер усилил, распространил на все функции Эйлера.

Ограничений у этого частного случая меньше, чем у теореме Эйлера. т.к. тут автоматически m и р – взаимно просты.

Допустим если а вне диапазона (a>m),

если а и m – взаимно просты то будет справедливо и для этого случая.

А если m – простое(р), то а не должно делится на р. Т.е. если а делится на р, то это уже не соответствует определению взаимно простых чисел.

Условие

В теории чисел известна функция Эйлера $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 )