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

Лена Наумова
Лена Наумова

Latest posts by Лена Наумова (see all)

Условие

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

 

Программный код

 

Ю2.6

Условие

Четырёхугольник [latex]ABCD[/latex] задан координатами своих вершин на плоскости: [latex]A(x_a,y_a)[/latex], [latex]B(x_b,y_b)[/latex] и [latex]C(x_c,y_c)[/latex], [latex]D(x_d,y_d)[/latex]. Определить тип четырёхугольника: прямоугольник, параллелограмм, трапеция, произвольный четырёхугольник. Учесть погрешность вычислений.

Замечание:  Для устранения дополнительных источников погрешности рекомендуется использовать аппарат векторной алгебры: коллинеарность, равенство и ортогональность векторов — сторон четырёхугольника.

Входные данные

В одной строке заданы 8 чисел [latex]x_a, x_b, x_c, x_d, y_a, y_b, y_c, y_d[/latex] — координаты вершин четырёхугольника [latex]ABCD[/latex],  значения которых не превышают по модулю [latex]50[/latex].

Выходные данные

  1. В первой строке вывести: «Тип четырёхугольника: «(без кавычек).
  2. Во второй строке вывести:  «Произвольный четырёхугольник» или «Прямоугольник» или «Параллелограмм» или «Трапеция»(без кавычек). Одно исключает другое.

Также условие задачи можно посмотреть, скачав ознакомительную версию задачника А.Юркина здесь.

Тестирование

Координаты [latex]x_a, x_b, x_c, x_d, y_a, y_b, y_c, y_d[/latex] Вердикт (тип четырёхугольника)
1. -5 -4 -1 -2 -4 3 -1 -8 Параллелограмм
2.  -2 -3 7 3 -2 1 7 1  Трапеция
 3. 0 0 1 1 0 1 1 0  Прямоугольник
 4.  50 -20 3 -50 7 6 2 3  Произвольный четырёхугольник
5. 2 -3 -6 -1 4 7 6 3 Параллелограмм
6. 1 -5 6 20 2 0 13 -9 Произвольный четырёхугольник
7. 0 1 2 1 0 1 1 0 Параллелограмм
8. -6 0 6 0 1 5 -4 -8 Прямоугольник

Реализация

Алгоритм решения

  1. Задан четырёхугольник [latex]ABCD[/latex] с такими координатами вершин: [latex]A(x_a,y_a)[/latex], [latex]B(x_b,y_b)[/latex], [latex]C(x_c,y_c)[/latex] и [latex]D(x_d,y_d)[/latex]. В данной задаче будет уместным использование аппарата векторной алгебры.  Пусть стороны четырёхугольника — векторы.
  2. Очевидно, что для того, чтобы определить тип данного четырёхугольника, необходимо воспользоваться известными свойствами, а именно: свойствами прямоугольника, параллелограмма и трапеции. Так как в задаче используется аппарат векторной алгебры, обращаемся к таким свойствам векторов, как коллинеарность и равенство.
  3. Сразу же установим: является ли четырёхугольник трапецией. Проверим одну из двух пар сторон на параллельность. Для этого воспользуемся условием коллинеарности векторов на плоскости: [latex]\frac{a_x}{b_x}=\frac{a_y}{b_y}[/latex], если [latex]a_i, b_i\ne0[/latex].  Координаты векторов [latex]\vec{b}[/latex] и [latex]\vec{d}[/latex] должны быть пропорциональны, что означает, что соответствующие стороны параллельны. Следовательно, [latex]\frac{x_c — x_b}{x_d — x_a}=\frac{y_c — y_b}{y_d — y_a}[/latex]. Или же координаты векторов [latex]\vec{a}[/latex] и [latex]\vec{c}[/latex] должны быть пропорциональны. Проверяем: [latex]\frac{x_b — x_a}{x_c — x_d}=\frac{y_b — y_a}{y_c — y_d}[/latex]. Если условие не выполняется, четырёхугольник произвольный. Если, напротив, координаты хотя бы одной пары векторов пропорциональны, четырёхугольник является трапецией.
  4. Если четырёхугольник — параллелограмм, то обе пары его противоположных сторон параллельны. Проверим, выполняется ли: [latex]\frac{x_b — x_a}{x_c — x_d}=\frac{y_b — y_a}{y_c — y_d}[/latex] и [latex]\frac{x_c — x_b}{x_d — x_a}=\frac{y_c — y_b}{y_d — y_a}[/latex]. Если условие выполняется, то заданный четырёхугольник — параллелограмм.
  5. Частным случаем параллелограмма является прямоугольник. Диагонали [latex] AC, BD[/latex] обозначим как [latex] l, m[/latex] соответственно. Пусть [latex] l, m[/latex] — векторы.  Вычислим длины векторов [latex]\vec{l}[/latex], [latex]\vec{m}[/latex], пользуясь формулой.  Получаем: [latex]\vec{|l|}= \sqrt{(x_c — x_a)\cdot (x_c -x_a) + (y_c — y_a)\cdot (y_c -y_a)}[/latex], [latex]\vec{|m|}= \sqrt{(x_d — x_b)\cdot (x_d -x_b) + (y_d — y_b)\cdot (y_d -y_b)}[/latex]. При условии, что [latex]\vec{l}=\vec{m}[/latex], имеем прямоугольник.

Более детально со свойствами и видами четырёхугольников можно ознакомиться здесь, а с основными сведениями из векторной алгебры — здесь.

Для запроса на выполнение следует перейти по ссылке.