Целочисленная арифметика

Разберём простую прекрасную задачу, в которой есть математика и строгое доказательство. Читаем условие: Для начала надо убедиться, что возможно разложить любое число, большее 7, на сумму пятёрок и троек. Докажем это с помощью математической индукции. База индукции: N = 8 = 5 + 3. Выполняется. Шаг индукции: пусть для всех чисел от 8 от N выполнено, докажем, что и для N+1 имеется разложение. Если в разложении N имеется хотя бы одна пятёрка, то можно заменить её на две тройки, таким образом получим разложение для N+1...

Обобщение классической школьной задачи по математике про три котлеты и одну сковородку. Попробуем решить её одной простой формулой. Но сначала читаем условие: Заметим, что домножать на m можно в самом конце, поэтому дальше будем считать, что m = 1. Для начала вспомним исходную задачу: Вам необходимо за 3 минуты пожарить 3 котлеты. Каждая котлета с одной стороны жарится ровно минуту. Но сковородка у нас маленькая, на ней помещаются одновременно всего лишь 2 котлеты. Как в таком случае выйти из положения?...

И снова задача на длинную арифметику и/или на математику. Сначала внимательно читаем условие: Важно при прочтении обратить внимание, что надо найти НОД не входных чисел, а чисел, состоящих из n и m единиц. Если мы пишем решение на Python, то можем воспользоваться всей мощностью языка и сделать ровно то, как описано в задаче: Здесь мы довольно хитро построили длинные числа - сначала построили строки из единичек нужной длины, а потом преобразовали их к числовому типу данных. Чтобы лучше понять алгоритм Евклида, напишем решение без использования длинной арифметики...

Рассмотрим решение задачи на простые числа, так как это одна из самых распространённых тем в олимпиадном программировании. Читаем условие задачи: Давайте сначала напишем функцию, которая проверяет, является ли число простым. Напомню определение простого числа: Простое число — это натуральное число, имеющее ровно два различных натуральных делителя. Иначе говоря, натуральное число a является простым, если оно отлично от 1 и делится без остатка только на 1 и на самого себя. Таким образом, необходимо проверить делимость числа a на все числа от 2 до a (не включая)...

Ещё одна задача на длинную арифметику (или нет). Читаем условие: Понятно, что десять тысяч в десятитысячной степени - это очень большое число, которые не помещается в стандартные типы данных. Всё это, конечно, не относится к Python, поэтому давайте попробуем решить задачу в лоб. Считываем входные два числа и преобразовываем их к числовому типу: И можно попробовать сразу вывести ответ: Здесь мы возводим одно число в степень и берём остаток от деления на 10, тем самым оставляя последнюю цифру. И, на удивление, решение задачи просто влетает...

Задача, обратная к Задача 147. Числа Фибоначчи, но решается почти тем же кодом. Условие: На первый взгляд пугающее здесь то, что входные данные могут быть больше миллиарда. И столько итераций в простом цикле точно не успеет отработать за секунду. Однако, это ограничение на предположительное число Фибоначчи, а не его номер. И если позапускать код из задачи Задача 147. Числа Фибоначчи, то можно понять, что уже 46-ое число Фибоначчи превышает данное ограничение. То есть цикл, который будет итеративно...