Арифметические алгоритмы (Теория чисел)

ID 31849. Несократимые дроби

Примеры

ID 38326. Домино

Рассмотрим N-домино. В таком домино каждая костяшка состоит из двух половинок, на каждой из которых нарисовано от 0 до N точек. Полный комплект костяшек такого домино содержит все возможные костяшки, каждую — по одному разу. Например, для N=2 в комплект войдут следующие костяшки: (0,0), (0,1), (0,2), (1,1), (1,2) и (2,2)

Напишите программу, которая по заданному N определит, сколько всего точек изображено на всех костяшках полного комплекта N-домино.

Входные данные
Вводится натуральное число N (1<=N<=30).

Выходные данные
Программа должна напечатать одно число - общее количество точек на всех костяшках полного комплекта N-домино.

Примеры

ID 38503. Конфеты детям

На детском празднике дети водили хороводы. Как только музыка закончила играть, дети всё ещё стояли в кругу. Тут Лена вспомнила, что родители дали ей коробку с k конфетками «Wilky May». Лена не жадина, поэтому она решила раздать все свои конфетки друзьям из хоровода. Лена знает, что некоторые её друзья сладкоежки, а некоторые нет. Сладкоежки берут из коробки две конфетки, если в коробке есть хотя бы две конфетки, а иначе берут одну. Остальные друзья Лены всегда берут ровно одну конфетку из коробки.

Чтобы начать раздавать конфетки, Лена вышла из хоровода, после чего в хороводе остались n ее друзей. Чтобы раздавать конфетки было проще, Лена присвоила каждому другу в хороводе номер в порядке по часовой стрелке, начиная с её лучшего друга Ромы, который получил номер 1.

Лена дала коробку другу, который получил номер l, после чего каждый друг Лены, начиная с друга с номером l, брал конфетки из коробки и передавал коробку следующему в порядке по часовой стрелке другу. После того, как друг с номером r взял конфетки, в коробке конфеток не осталось. Обратите внимание, что возможно, что некоторые друзья Лены брали конфетки из коробки несколько раз, то есть коробка могла пройти несколько полных кругов по хороводу.

Лена не знает, кто из ее друзей сладкоежки, но ее интересует, сколько максимум из её друзей могут быть сладкоежками. Если же такой ситуации не могло случиться, и Лена ошиблась в своих наблюдениях, сообщите ей об этом.

Входные данные
В единственной строке задаются четыре целых числа n, l, r, k (1 ≤ n, k ≤ 10¹¹ , 1 ≤ l, r ≤ n ) — количество детей в хороводе, номер друга, которому Лена отдала коробку конфет, номер друга, который взял последнюю конфетку, и количество конфет в коробке, соответственно.

Выходные данные
Выведите одно целое число — максимально возможное количество сладкоежек среди друзей Лены или « -1 » (без кавычек), если Лена ошиблась в своих наблюдениях.
 

Примеры

ID 42233. Вычислите значение многочлена - 1.

Вычислите значение многочлена вида: a_nxⁿ+a_n-1x^n-1+...+a₁x+a₀ по значениям коэффициентов и значению аргумента.
Входные данные:
1 строка - число N (0<=N<=10000) - степень многочлена
2 строка - N+1 целое число разделенные пробелом - коэффициенты многочлена a_n,a_n-1,...,a₁,a₀
3 строка - натуральное число K -  количество значений аргументов (K<=10⁶), для которых надо вычислить значение многочлена
В следующих K строках даны значения аргумента - вещественные числа
Выходные данные:
Вычислите значения многочлена для заданных аргументов. В качестве ответа выведите:
- в 1 строке - аргумент, при котором многочлен принимает минимальное значение. Если таких значений несколько, то выведите минимальное из значений. 
- в 2 строке - значение многочлена для аргумента из 1-й строки. Значение округлите до 0,0000001

ID 42263. Кривая дракона

Сегодня мальчик Саша на уроке математики узнал про фракталы. Учитель показывал так называемую «кривую дракона». Она представляет собой геометрическую фигуру, которая строится следующим образом: на первом шаге проводится отрезок из начала координатной плоскости в точку (0; 1). Далее на каждом шаге из конца фрактала повторяется уже нарисованная часть фигуры, повернутая на 90 градусов против часовой стрелки (см. рисунок).

После уроков Саша попробовал сам изобразить «кривую дракона», и теперь он хочет знать, в какой точке координатной плоскости он закончил рисовать фрактал, проделав описанные выше N шагов. Требуется написать программу, которая по заданному числу N определяет координаты конца фрактала после выполнения N шагов.

Примеры

ID 23334. Интересные числа (С', C)

ID 47674. Умножение с аккумулированием. Рекурсия

Напишите программу для нахождения суммы числа 1580 и произведения двух натуральных чисел.
Входные данные:
Два натуральных числа x, y
Выходные данные:
Сумма числа 1580 и произведения чисел x и y
Для выполнения задания необходимо дописать рекурсивную подпрограмму multi.
 
Запрещено использовать другие подпрограммы, циклы, ряд стандартных функций и операцию умножения.
Примечание:
Для проверки четности числа можно воспользоваться оператором a&1 (возврашает True для нечётных а и False для четных)
Для целочисленного деления на 2 можно воспользоваться оператором a>>1 (равносильно оператору a//2) 
 

ID 47678. Умножение с аккумулированием. Рекурсия

Напишите программу для нахождения суммы числа 1580 и произведения двух натуральных чисел.
Входные данные:
Два натуральных числа x, y
Выходные данные:
Сумма числа 1580 и произведения чисел x и y
Для выполнения задания необходимо дописать рекурсивную подпрограмму multi.
 
Запрещено использовать другие подпрограммы, циклы, ряд стандартных функций и операцию умножения.
Примечание:
Для проверки четности числа можно воспользоваться оператором a&1 (возврашает True для нечётных а и False для четных)
Для целочисленного деления на 2 можно воспользоваться оператором a>>1 (равносильно оператору a//2) 
 

ID 47669. Умножение на натуральное. Франгмент подпрограммы

Операция умножения это замена многократного сложения.
Пусть определена операция сложения на объектами типа 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         

ID 48295. Умножение с аккумулированием. Рекурсия

Напишите программу для нахождения суммы числа 1580 и произведения двух натуральных чисел.
Входные данные:
Два натуральных числа x, y
Выходные данные:
Сумма числа 1580 и произведения чисел x и y
Для выполнения задания необходимо дописать рекурсивную подпрограмму multi.
 
Запрещено использовать другие подпрограммы, циклы, ряд стандартных функций и операцию умножения.
Примечание:
Для проверки четности числа можно воспользоваться оператором a&1 (возврашает True для нечётных а и False для четных)
Для целочисленного деления на 2 можно воспользоваться оператором a>>1 (равносильно оператору a//2) 
 

ID 48048. Задачи на печать!

Олимпиады бывают не только личные, но и командные. В командной олимпиаде по программированию обычно принимают участие команды из трёх человек, которым предоставляется один компьютер и один комплект условий задач, причём задач обычно существенно больше, чем в личных олимпиадах.

Условие каждой из задач помещается на одной, двух или трёх страницах. При этом условие может быть напечатано на двух сторонах одного листа, но для удобства команд на одном листе может располагаться условие только одной из задач. Для экономии бумаги, если условие задачи занимает две страницы, оно должно быть напечатано на двух сторонах одного листа, а если из трёх страниц - на двух сторонах одного листа и на одной стороне другого листа, вторая сторона которого останется чистой. При этом можно напечатать первую страницу такой задачи отдельно на чистом листе, а оставшиеся две страницы - на одном листе или, наоборот, первые две страницы распечатать на одном листе, а третью - на чистом листе. Задачи и все их страницы печатаются последовательно.

Условия всех задач распечатываются на принтере в виде нескольких последовательных заданий. Для каждого задания необходимо задать диапазон печати: номера первой и последней страниц, которые будут напечатаны в этом задании (будут напечатаны все страницы в этом диапазоне), а также тип печати - односторонняя или двусторонняя. 

Вам необходимо минимизировать количество заданий для печати условий.

Формат входных данных
Первая строка входных данных содержит целое число n (1 ≤ n ≤ 10⁶) - количество задач в олимпиаде.
Вторая строка входных данных содержит целое число n (1 ≤ x_i ≤ 3) - количество страниц в i-й задаче.
Формат выходных данных
Выведите единственное число - минимальное количество последовательных диапазонов, каждый из которых можно напечатать одной командой односторонней или двусторонней печати так, что условия всех задач будут напечатаны в удобном для командной олимпиады виде.

Замечание
В первом примере на олимпиаду предложены 4 задачи, условия которых состоят из 1, 3, 2 и 1 страниц соответственно. Всего необходимо распечатать 7 страниц. Их можно распечатать за два задания: cтраницы 1-2 - односторонней печатью (это единственная страница первой задачи и первая из трёх страниц второй задачи), оставшиеся страницы 3-7 - двусторонней.

Во втором примере на олимпиаду предложены 2 задачи, условия которых состоят из 3 страниц каждая. Всего необходимо распечатать 6 страниц. Их можно распечатать за два задания: cтраницы 1-1- односторонней печатью (это первая из трёх страниц первой задачи), оставшиеся страницы 2-6 - двусторонней. При этом в первой задаче первая страница будет напечатана на одной стороне,  потому что она напечатана односторонней печатью, а во второй задаче последняя страница будет напечатана на одной стороне, потому что в этом задании нечётное число страниц печатается на двух сторонах, поэтому вторая сторона этого листа будет пустой.

ID 44510. Возрастающие пути

Дано дерево на 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 <= 10⁷) - номера вершин, которые соединяет очередное ребро, и его вес.

Выведите одно целое число k - максимальную длину возрастающего пути.

Простым путем называется такой путь, что все вершины в нем различны.

В 1-м примере есть путь длины 2: 3 — 1 — 2. Тогда для него подходящий x = 2. Можно показать, что возрастающего пути большей длины не существует.

Во 2-м примере есть путь длины 3: 3 — 4 — 5 — 6. Тогда для него подходящий x = 2. Можно показать, что возрастающего пути большей длины не существует.

Примеры

4
1 2 8
1 3 6
1 4 3

2

6
1 2 2
2 3 4
3 4 2
4 5 4
5 6 8

3

ID 48970. Разбиение массива

Дан массив \(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\), но их отношение не является простым числом.

ID 33122. Квадраты и кубы

ID 33303. Последовательность

ID 55106. Совершенные числа

Число называется совершенным, если оно равно сумме всех своих делителей, меньших его самого. Требуется найти все совершенные числа от M до N.

Входные данные
В первой строке находятся разделённые пробелом числа M и N. M и N целые, 1 <= M <= N <= 10⁹, (N - M) * sqrt(N) <= 10⁷.

Выходные данные
В каждой строке вывести по одному числу в порядке возрастания. Если совершенных чисел в промежутке нет, вывести "Absent".

ID 59478. Разность квадратов есть произведение, а произведение есть ...

Напишите функцию  multi_two(x,y), которая получает два целых числа x, y, а возвращает их произведение.
Для решения задания создайте функцию raise_to_two(z), которая получает целое число z, а возвращает значение  z2
Запрещено использование модулей, операций **,  *,  /,  %,  bin,  str, pow, sqr,<,  списков, множеств, словарей  
Примечание:
Для проверки четности числа можно воспользоваться оператором a&1 (возврашает True для нечётных а и False для четных)
Для целочисленного деления на 2 можно воспользоваться оператором a>>1 (равносильно оператору a//2) 

 

ID 60226. Урок физкультуры - 2

В известной школе прошёл урок физкультуры. Как полагается, всех построили в шеренгу и попросили рассчитаться на <<первый–\(k\)-й>>, где \(k > 1\).

Как известно, расчёт на <<первый–\(k\)-й>> происходит следующим образом: первые \(k\) человек имеют номера \(1, 2, 3, \ldots, k\), следующие \(k - 1\) человек имеют номера \(k - 1, k - 2, \ldots, 1\), следующие \(k - 1\) человек имеют номера \(2, 3, \ldots, k\) и т.д. Таким образом, расчёт повторяется через каждые \(2k - 2\) позиции. Примеры расчёта приведены в разделе <<Замечание>>.

Мальчик Вася постоянно всё забывает. Например, он забыл число \(k\), описанное выше. Но он помнит позицию, которую занимал в шеренге, а также какой номер он получил при расчёте. Помогите Васе понять, сколько натуральных чисел \(k\) подходят под данные ограничения.

Обратите внимание, что не существует расчёта для \(k = 1\).

Формат входных данных
Первая строка содержит одно целое число \(n\) (\(2 \leq n \leq 10^9\)) — позиция Васи в ряду в нумерации, начинающейся с \(1\).

Вторая строка содержит одно целое число \(x\) (\(1 \leq x < n\)) — номер, который Вася получил при расчёте.

Формат выходных данных
Выведите единственное целое число — количество различных \(k > 1\), которые подходят под данные ограничения.

Можно доказать, что при данных ограничениях ответ является конечным.

Примечание
В первом примере подходят \(k\) равные \(2, 3, 5, 6\).

Пример расчёта для этих \(k\):