| | |
Несократимые дроби
Арифметические алгоритмы (Теория чисел)
Функция Эйлера
Дробь \({m \over n}\) называется правильной несократимой, если \(0 < m < n\) и \(НОД (m, n) = 1\). Найдите количество правильных несократимых дробей со знаменателем n .
Входные данные
В первой строке задается число знаменателей для которых надо найти количество правильных несократимых дробей N (\(N <=100\)). Каждая последующая строка число n (\(n < 10^9\)).
Выходные данные
Для каждого n в отдельной строке вывести ответ на поставленную задачу.
Примеры
№ |
Входные данные |
Выходные данные |
1 |
4
23
23456
7
17
|
22
11712
6
16 |
| |
|
Домино
Арифметические алгоритмы (Теория чисел)
Рассмотрим N-домино. В таком домино каждая костяшка состоит из двух половинок, на каждой из которых нарисовано от 0 до N точек. Полный комплект костяшек такого домино содержит все возможные костяшки, каждую — по одному разу. Например, для N=2 в комплект войдут следующие костяшки: (0,0), (0,1), (0,2), (1,1), (1,2) и (2,2)
Напишите программу, которая по заданному N определит, сколько всего точек изображено на всех костяшках полного комплекта N-домино.
Входные данные
Вводится натуральное число N (1<=N<=30).
Выходные данные
Программа должна напечатать одно число - общее количество точек на всех костяшках полного комплекта N-домино.
Примеры
№ |
Входные данные |
Выходные данные |
1 |
2 |
12 |
| |
|
Конфеты детям
Остатки
Арифметические алгоритмы (Теория чисел)
На детском празднике дети водили хороводы. Как только музыка закончила играть, дети всё ещё стояли в кругу. Тут Лена вспомнила, что родители дали ей коробку с k конфетками «Wilky May». Лена не жадина, поэтому она решила раздать все свои конфетки друзьям из хоровода. Лена знает, что некоторые её друзья сладкоежки, а некоторые нет. Сладкоежки берут из коробки две конфетки, если в коробке есть хотя бы две конфетки, а иначе берут одну. Остальные друзья Лены всегда берут ровно одну конфетку из коробки.
Чтобы начать раздавать конфетки, Лена вышла из хоровода, после чего в хороводе остались n ее друзей. Чтобы раздавать конфетки было проще, Лена присвоила каждому другу в хороводе номер в порядке по часовой стрелке, начиная с её лучшего друга Ромы, который получил номер 1.
Лена дала коробку другу, который получил номер l, после чего каждый друг Лены, начиная с друга с номером l, брал конфетки из коробки и передавал коробку следующему в порядке по часовой стрелке другу. После того, как друг с номером r взял конфетки, в коробке конфеток не осталось. Обратите внимание, что возможно, что некоторые друзья Лены брали конфетки из коробки несколько раз, то есть коробка могла пройти несколько полных кругов по хороводу.
Лена не знает, кто из ее друзей сладкоежки, но ее интересует, сколько максимум из её друзей могут быть сладкоежками. Если же такой ситуации не могло случиться, и Лена ошиблась в своих наблюдениях, сообщите ей об этом.
Входные данные
В единственной строке задаются четыре целых числа n, l, r, k (1 ≤ n, k ≤ 1011 , 1 ≤ l, r ≤ n ) — количество детей в хороводе, номер друга, которому Лена отдала коробку конфет, номер друга, который взял последнюю конфетку, и количество конфет в коробке, соответственно.
Выходные данные
Выведите одно целое число — максимально возможное количество сладкоежек среди друзей Лены или « -1 » (без кавычек), если Лена ошиблась в своих наблюдениях.
Примеры
№ |
Входные данные |
Выходные данные |
Пояснение |
1 |
4 1 4 12 |
2 |
Любые два друга могут быть сладкоежками, тогда каждый два раза получит коробку конфет и последним, кто возьмёт конфету, будет четвёртый человек. |
2 |
5 3 4 10 |
3 |
Сладкоежками могут быть любые три друга, кроме друга, стоящего на третьем месте. |
3 |
10 5 5 1 |
10 |
Только один друг возьмёт одну конфетку, но он может быть сладкоежкой, просто он не может взять две конфеты. Все остальные в кругу тоже могут быть сладкоежками, но они не могут взять ни одной конфеты. |
4 |
5 4 5 6 |
-1 |
Лена ошиблась и такой ситуации быть не могло. |
| |
|
Вычислите значение многочлена - 1.
Задачи на процедуры и функции
Арифметические алгоритмы (Теория чисел)
Вычислите значение многочлена вида: anxn+an-1xn-1+...+a1x+a0 по значениям коэффициентов и значению аргумента.
Входные данные:
1 строка - число N (0<=N<=10000) - степень многочлена
2 строка - N+1 целое число разделенные пробелом - коэффициенты многочлена an,an-1,...,a1,a0
3 строка - натуральное число K - количество значений аргументов (K<=106), для которых надо вычислить значение многочлена
В следующих K строках даны значения аргумента - вещественные числа
Выходные данные:
Вычислите значения многочлена для заданных аргументов. В качестве ответа выведите:
- в 1 строке - аргумент, при котором многочлен принимает минимальное значение. Если таких значений несколько, то выведите минимальное из значений.
- в 2 строке - значение многочлена для аргумента из 1-й строки. Значение округлите до 0,0000001
ВХОДНЫЕ ДАННЫЕ |
ВЫХОДНЫЕ ДАННЫЕ |
2
1 0 0
4
9.0
-11.0
-9.0
16.0 |
-9.0
81.0 |
10
7 -7 -4 3 -6 -9 -7 4 0 -9 8
2
0.01
0.0
|
0.01
7.9100039
|
| |
|
Кривая дракона
Циклы
Арифметические алгоритмы (Теория чисел)
Сегодня мальчик Саша на уроке математики узнал про фракталы. Учитель показывал так называемую «кривую дракона». Она представляет собой геометрическую фигуру, которая строится следующим образом: на первом шаге проводится отрезок из начала координатной плоскости в точку (0; 1). Далее на каждом шаге из конца фрактала повторяется уже нарисованная часть фигуры, повернутая на 90 градусов против часовой стрелки (см. рисунок).
После уроков Саша попробовал сам изобразить «кривую дракона», и теперь он хочет знать, в какой точке координатной плоскости он закончил рисовать фрактал, проделав описанные выше N шагов. Требуется написать программу, которая по заданному числу N определяет координаты конца фрактала после выполнения N шагов.
Входные данные
Вводится одно целое число N (1 <= N <= 30).
Выходные данные
Выведите два числа через пробел - координаты конца фрактала.
Примеры
№ |
Входные данные |
Выходные данные |
1 |
2 |
1 1 |
2 |
4 |
2 -2 |
| |
|
Интересные числа (С', C)
Вывод формулы
Циклы
Арифметические алгоритмы (Теория чисел)
Маленький Вася очень любит числа, а особенно сильно он любит интересные числа. Вася считает число x интересным, если сумма квадратов его цифр делится на число 7. Например, число 123 -
интересное, потому что 1 2 + 2 2 + 3 2 = 14 делится на 7, а число 16 - нет, потому что 1 2 + 6 2 = 37 не делится на 7. Однажды Вася увидел на доске число x, он сразу же захотел узнать величину минимального интересного числа, которое строго больше чем x. Так как Вася еще слишком юн, он обратился к вам за помощью в решение этой задачи.
Формат входных данных
Во входном файле содержится единственное целое число x - число, написанное на доске 0<= x <= 105
Формат выходных данных
В единственную строку выходного файла выведите минимальное интересное число, которое строго больше чем x.
| |
|
Умножение с аккумулированием. Рекурсия
Арифметические алгоритмы (Теория чисел)
Напишите программу для нахождения суммы числа 1580 и произведения двух натуральных чисел.
Входные данные:
Два натуральных числа x, y
Выходные данные:
Сумма числа 1580 и произведения чисел x и y
Для выполнения задания необходимо дописать рекурсивную подпрограмму multi.
Запрещено использовать другие подпрограммы, циклы, ряд стандартных функций и операцию умножения.
Примечание:
Для проверки четности числа можно воспользоваться оператором a&1 (возврашает True для нечётных а и False для четных)
Для целочисленного деления на 2 можно воспользоваться оператором a>>1 (равносильно оператору a//2)
| |
|
Умножение с аккумулированием. Рекурсия
Арифметические алгоритмы (Теория чисел)
Напишите программу для нахождения суммы числа 1580 и произведения двух натуральных чисел.
Входные данные:
Два натуральных числа x, y
Выходные данные:
Сумма числа 1580 и произведения чисел x и y
Для выполнения задания необходимо дописать рекурсивную подпрограмму multi.
Запрещено использовать другие подпрограммы, циклы, ряд стандартных функций и операцию умножения.
Примечание:
Для проверки четности числа можно воспользоваться оператором a&1 (возврашает True для нечётных а и False для четных)
Для целочисленного деления на 2 можно воспользоваться оператором a>>1 (равносильно оператору a//2)
| |
|
Умножение на натуральное. Франгмент подпрограммы
Арифметические алгоритмы (Теория чисел)
Операция умножения это замена многократного сложения.
Пусть определена операция сложения на объектами типа A.
Необходимо выполнить операцию\(A\cdot n =\) \(\underbrace {A+...+A}_{n\ раз}\) , то есть организовать умножение объекта типа A на натуральное число n
Ваша программа должна быть достаточно эффективной и выполнять не более, чем \(2\cdot log_2(n) \) операций сложений.
Даны объект A /представлен как строка/ и натуральное число n. Напишите фрагмент кода, эффективно выполняющий операцию \(A\cdot n\)
В шаблоне представлен фрагмент кода, выполняющий операцию \(A\cdot n\) за n операций сложения
def multi( A, n ): # умножение объекта A на натуральное число n
rez=None
for i in range(n):
rez=my_add(rez,A) # my_add(x,y) - выполняет сложение объектов x+y (если один есть None, то возвращает значение другого)
return rez
Примечание:
Операция * для объектов либо неопределена, либо вернет неверный результат. Поэтому запрещено использовать операцию * (умножение).
Подпрограмма my_add( x, y ) возвращает результат "сложения" объектов x и y (если они определены) или один из объектов (если другой неопределен, то есть my_add(None, y) возвращает y )
| |
|
Головасты
Целые числа
Строки
Арифметические алгоритмы (Теория чисел)
Находясь на планете Малого Арктура, Алиса и Громозека отправились в зоопарк. Этот зоопарк известен тем, что в нем можно увидеть головастов - рептилий, которые обитают только на этой планете. Чтобы получить доступ к рептилиям, им необходимо ввести код на входе в зоопарк. Однако, код постоянно меняется и всегда равен минимальному числу, не меньшему, чем записанное на экране перед входом и состоящему только из цифр 3, 6 и 9.
Помогите Алисе и Громозеке определить код доступа к рептилиям.
Входные данные
Ввод содержит одно число n (1 <= n <= 1018).
Выходные данные
Выведите одно число - код доступа к рептилиям.
Примеры
№ |
Входные данные |
Выходные данные |
1 |
2007
|
3333
|
2 |
97
|
99
|
| |
|
Умножение с аккумулированием. Рекурсия
Арифметические алгоритмы (Теория чисел)
Напишите программу для нахождения суммы числа 1580 и произведения двух натуральных чисел.
Входные данные:
Два натуральных числа x, y
Выходные данные:
Сумма числа 1580 и произведения чисел x и y
Для выполнения задания необходимо дописать рекурсивную подпрограмму multi.
Запрещено использовать другие подпрограммы, циклы, ряд стандартных функций и операцию умножения.
Примечание:
Для проверки четности числа можно воспользоваться оператором a&1 (возврашает True для нечётных а и False для четных)
Для целочисленного деления на 2 можно воспользоваться оператором a>>1 (равносильно оператору a//2)
| |
|
Задачи на печать!
Конструктив
Арифметические алгоритмы (Теория чисел)
Олимпиады бывают не только личные, но и командные. В командной олимпиаде по программированию обычно принимают участие команды из трёх человек, которым предоставляется один компьютер и один комплект условий задач, причём задач обычно существенно больше, чем в личных олимпиадах.
Условие каждой из задач помещается на одной, двух или трёх страницах. При этом условие может быть напечатано на двух сторонах одного листа, но для удобства команд на одном листе может располагаться условие только одной из задач. Для экономии бумаги, если условие задачи занимает две страницы, оно должно быть напечатано на двух сторонах одного листа, а если из трёх страниц - на двух сторонах одного листа и на одной стороне другого листа, вторая сторона которого останется чистой. При этом можно напечатать первую страницу такой задачи отдельно на чистом листе, а оставшиеся две страницы - на одном листе или, наоборот, первые две страницы распечатать на одном листе, а третью - на чистом листе. Задачи и все их страницы печатаются последовательно.
Условия всех задач распечатываются на принтере в виде нескольких последовательных заданий. Для каждого задания необходимо задать диапазон печати: номера первой и последней страниц, которые будут напечатаны в этом задании (будут напечатаны все страницы в этом диапазоне), а также тип печати - односторонняя или двусторонняя.
Вам необходимо минимизировать количество заданий для печати условий.
Формат входных данных
Первая строка входных данных содержит целое число n (1 ≤ n ≤ 106) - количество задач в олимпиаде.
Вторая строка входных данных содержит целое число n (1 ≤ xi ≤ 3) - количество страниц в i-й задаче.
Формат выходных данных
Выведите единственное число - минимальное количество последовательных диапазонов, каждый из которых можно напечатать одной командой односторонней или двусторонней печати так, что условия всех задач будут напечатаны в удобном для командной олимпиады виде.
Замечание
В первом примере на олимпиаду предложены 4 задачи, условия которых состоят из 1, 3, 2 и 1 страниц соответственно. Всего необходимо распечатать 7 страниц. Их можно распечатать за два задания: cтраницы 1-2 - односторонней печатью (это единственная страница первой задачи и первая из трёх страниц второй задачи), оставшиеся страницы 3-7 - двусторонней.
Во втором примере на олимпиаду предложены 2 задачи, условия которых состоят из 3 страниц каждая. Всего необходимо распечатать 6 страниц. Их можно распечатать за два задания: cтраницы 1-1- односторонней печатью (это первая из трёх страниц первой задачи), оставшиеся страницы 2-6 - двусторонней. При этом в первой задаче первая страница будет напечатана на одной стороне, потому что она напечатана односторонней печатью, а во второй задаче последняя страница будет напечатана на одной стороне, потому что в этом задании нечётное число страниц печатается на двух сторонах, поэтому вторая сторона этого листа будет пустой.
| |
|
Возрастающие пути
Алгоритмы на графах
Арифметические алгоритмы (Теория чисел)
Применение обхода в глубину
Обход в глубину
Дано дерево на n вершинах (связный неориентированный ациклический граф c n−1 рёбрами), где у каждого ребра есть вес w . Назовём простой путь длины k возрастающим , если существует такое целое x>= 2, что вес первого ребра пути делится на x , второго ребра — делится на x2 , ……, вес k -го ребра делится на xk .
Требуется найти максимальную длину k возрастающего пути, где k — количество рёбер в нём.
Входные данные
В первой строке вводится единственное целое число n (1 <= n <= 100000) - число вершин в дереве.
В следующих n−1 строках вводятся по три целых числа u , v , w ( 1<= v <= n, 1<= w <= n, u ≠ v, 1 <= w <= 107) - номера вершин, которые соединяет очередное ребро, и его вес.
Выходные данные
Выведите одно целое число k - максимальную длину возрастающего пути.
Примечание
Простым путем называется такой путь, что все вершины в нем различны.
В 1-м примере есть путь длины 2: 3 — 1 — 2. Тогда для него подходящий x = 2 . Можно показать, что возрастающего пути большей длины не существует.
Во 2-м примере есть путь длины 3: 3 — 4 — 5 — 6. Тогда для него подходящий x = 2 . Можно показать, что возрастающего пути большей длины не существует.
Примеры
№ |
Входные данные |
Выходные данные |
1 |
4
1 2 8
1 3 6
1 4 3
|
2
|
2 |
6
1 2 2
2 3 4
3 4 2
4 5 4
5 6 8
|
3
|
| |
|
Разбиение массива
Арифметические алгоритмы (Теория чисел)
Дан массив \(A = [a_1, a_2, \ldots, a_n]\), содержащий \(n\) натуральных чисел.
Требуется раскрасить элементы массива в два цвета таким образом, чтобы не существовало двух элементов \(x\) и \(y\) одного цвета, таких что \(x\) нацело делился на \(y\) и выполнялось равенство \(\frac{x}{y} = p\), где \(p\) — простое число. Гарантируется, что такая раскраска существует.
Напомним, что целое число \(p > 1\) называется простым, если оно имеет ровно два делителя: \(1\) и \(p\).
Формат входных данных
Первая строка содержит одно целое число \(n\) (\(1 \le n \le 100\,000\)) — количество элементов в массиве.
Вторая строка содержит \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^6\)) — элементы массива.
Формат выходных данных
Выведите описание разбиения массива на два множества в следующем формате.
Выведите \(n\) целых чисел, \(i\)-е из которых равняется \(1\), если элемент \(a_i\) надо раскрасить в первый цвет и \(2\), если элемент \(a_i\) надо раскрасить во второй цвет.
Если существует несколько подходящих раскрасок, вы можете вывести любую из них.
В первом примере есть два элемента первого цвета: \(2\) и \(3\), и два элемента второго цвета: \(1\) и \(4\). Элементы первого цвета не делятся нацело друг на друга. \(4\) нацело делится на \(1\), но их отношение не является простым числом.
| |
|
Квадраты и кубы
Целые числа
Арифметические алгоритмы (Теория чисел)
Бинарный поиск
Линейный поиск
Вещественные числа
В лаборатории теории чисел одного университета изучают связь между
распределением квадратов и кубов натуральных чисел.
Пусть задано целое неотрицательное число k. Рассмотрим множество натуральных
чисел от a до b, включительно. Будем называть k-плотностью этого множества количество
пар натуральных чисел x и y, таких, что a ≤ x2 ≤ b, a ≤ y3 ≤ b, причем |x2– y3| ≤ k.
Например, 2-плотность множества натуральных чисел от 1 до 30 равна 3, так как
подходят следующие пары:
x = 1, y = 1, |x2– y3| = |1 – 1| = 0;
x = 3, y = 2, |x2– y3| = |9 – 8| = 1;
x = 5, y = 3, |x2– y3| = |25 – 27| = 2.
Требуется написать программу, которая по заданным натуральным числам a и b, а
также целому неотрицательному числу k, определяет k-плотность множества натуральных
чисел от a до b, включительно.
Формат входных данных
Входные данные содержат три строки. Первая строка содержит натуральное число a,
вторая строка содержит натуральное число b, третья строка содержит целое неотрицательное
число k (1 ≤ a ≤ b ≤ 1018, 0 ≤ k ≤ 1018).
Формат выходных данных
Выходные данные должны содержать одно целое число: искомую k-плотность
множества натуральных чисел от a до b, включительно.
| |
|
Последовательность
Рекурсия
Целые числа
Арифметические алгоритмы (Теория чисел)
Последовательность 011212201220200112… строится следующим образом: сначала пишется 0, затем повторяется следующее действие: уже написанную часть приписывают справа с заменой 0 на 1, 1 на 2, 2 на 0, и т.д.
Требуется написать программу, которая по заданному натуральному числу N определяет, какое число стоит на N-ом месте.
Входные данные
Дано натурально число число N (1 ≤ N ≤ 1018).
Выходные данные
Выведите число, которое стоит на k-ом месте в последовательности.
| |
|
Совершенные числа
Арифметические алгоритмы (Теория чисел)
Число называется совершенным, если оно равно сумме всех своих делителей, меньших его самого. Требуется найти все совершенные числа от M до N.
Входные данные
В первой строке находятся разделённые пробелом числа M и N. M и N целые, 1 <= M <= N <= 109, (N - M) * sqrt(N) <= 107.
Выходные данные
В каждой строке вывести по одному числу в порядке возрастания. Если совершенных чисел в промежутке нет, вывести "Absent".
| |
|