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

Напишите программу, вычисляющую остаток от деления заданного «длинного» числа на заданную цифру.

Входные данные
В первой строке задана цифра K (1≤K≤9). Во второй строке задано натуральное число N, состоящее из не более чем 250 цифр.

Выходные данные
Выведите остаток от деления N на K.

Требуется заполнить N элементов массива, пронумерованных числами от 1 до N (A[1]…A[N]), натуральными числами от 2 до N+1, использовав каждое число ровно один раз, так, чтобы значение каждого элемента массива делилось бы нацело на его номер (т.е. для каждого i A[i] делилось бы на i).

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

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

Выходные данные
Выведите одно число — искомое количество способов заполнения массива.

Примечание
Массив можно заполнить единственным способом: 3 2
 

Требуется заполнить N элементов массива, пронумерованных числами от 1 до N (A[1]…A[N]), натуральными числами от 2 до N+1, использовав каждое число ровно один раз, так, чтобы значение каждого элемента массива делилось бы нацело на его номер (т.е. для каждого i A[i] делилось бы на i).

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

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

Выходные данные
Выведите одно число — искомое количество способов заполнения массива.

Примечание
Массив можно заполнить единственным способом: 3 2
 

Напишите программу, вычисляющую остаток от деления заданного «длинного» числа на заданную цифру.

Входные данные
В первой строке задана цифра K (1≤K≤9). Во второй строке задано натуральное число N, состоящее из не более чем 100000 цифр.

Выходные данные
Выведите остаток от деления N на K.

Дана запись некоторого числа в двоичном дополнительном коде. Выведите десятичную запись этого числа.

Входные данные
Программа получает на вход строку из нулей и единиц. Длина строки не меньше 2 и не больше 16.

Выходные данные
Программа должна вывести десятичную запись числа, записанного в этой строке в двоичном дополнительном коде.

Напишите программу, которая по данным числам A и n записывает представление числа A в n-разрядном двоичном дополнительном коде.

Входные данные
Первая строка входных данных содержит число A, вторая строка –– число n, при этом    2 ≤ n ≤ 16,  −2^n-1 ≤ A ≤  2 ^n-1−1 .

Выходные данные
Программа должна вывести строку из n символов, содержащих запись числа A в n-разрядном двоичном дополнительном коде, первый символ –– старший знаковый разряд.

Напишите программу, переводящую запись числа между двумя произвольными системами счисления.

Входные данные
На вход программа получает три величины: n, A, k, где n и k — натуральные числа от 2 до 36, основания системы счисления, A — число, записанное в системе счисления с основанием n, A<2³¹.

Выходные данные
Необходимо вывести значение A в системе счисления с основанием k без лидирующих нулей.

Цифры записываются следующими символами: 0, 1, 2, ..., 9, A, B, C, ..., Z.

Преобразуйте дробь.

Входные данные
Дана запись двоичной дроби, как в задаче "Binary periodical fraction to decimal", но в целых числах точки может не быть. Необходимо представить ее в виде несократимой рациональной дроби n/m.

Выходные данные
Программа должна вывести значения n и m .

Дано рациональное число. Запишите его в виде двоичной периодической дроби.

Входные данные
На вход программа получает два натуральных числа n и m, каждое из которых не превосходит 1000.

Выходные данные
Программа должна вывести значение n/m, записанное в виде двоичной периодической дроби, при этом длина непериодической дробной части и длина периода должны быть минимально возможными. Если данное число является конечной двоичной дробью, периодическую часть выводить не надо.

Преобразуйте двоичное число.

Входные данные
Дана запись целого двоичного числа или двоичной периодической дроби, которая включает в себя:

1. Необязательную целую часть.
2. Необязательный символ точки, отделяющий целую часть от дробной. 

3. Необязательную дробную непериодическую часть. 

4. Необязательную периодическую дробную часть, записываемую в круглых скобках.

Выходные данные
Необходимо определить значение этой дроби, сохранить его в переменной типа double и вывести на экран с точностью не менее 12 знаков. Общая длина входной строки не превосходит 30 символов.

Переведите десятичное число в двоичную систему.

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

Выходные данные
Необходимо представить число в виде двоичной дроби с фиксированной точкой и вывести это представление. Ответ должен отличаться от правильного не более, чем на 2 − 32 , то есть необходимо вывести не менее 32 двоичных цифр после точки.

Переведите число из двоичной системы счисления в десятичную.

Входные данные
Дано число, представленное в виде двоичной дроби: запись длиной не более 30 символов, содержащая цифры 0 и 1 и, возможно, одну точку.

Выходные данные
Необходимо вывести данное число в виде десятичной дроби (тип переменной double с точностью не менее 12 знаков).

В калькулятор вводится натуральное число K и нажимается клавиша "+". Калькулятор всё ещё показывает K. Цель игры: получить на экране число, состоящее из одинаковых цифр. Для её достижения можно производить только одно действие - нажимать на клавишу "=" (возможно, 0 раз). После первого нажатия получается результат K + K, после очередного нажатия результат увеличивается на K. Требуется определить, удастся ли достичь цели, а если удастся, то какое число, состоящее из одинаковых цифр, будет получено первым. Количество отображаемых калькулятором цифр считать неограниченным, время работы батареек - тоже.

1 <= K <= 999.

Входные данные
В первой строке находится одно число - K.

Выходные данные
Если цели достичь невозможно, вывести "Impossible", если возможно, вывести два числа через пробел: цифру, из которой состоит искомое число, и количество цифр в числе.

Каждый член последовательности десятичных цифр d¹, d², d³..., начиная с четвёртого, равен последней цифре суммы трёх предыдущих. По заданным d¹, d², d³ найти N-й член последовательности.

Ограничения: 1 <= N <= 10¹⁵.

Входные данные
В первой строке находятся цифры d₁, d₂, d₃, разделённые пробелами, во второй - число N.

Выходные данные
Вывести одну цифру - d_N.

В последовательности чисел a₁, a₂, a₃, ... задан первый член, а остальные вычисляются по формуле a_i = (a_i - 1)2 mod 10 000. Найти N-й член последовательности.

Ограничения: 0 <= a₁ < 10 000, 1 <= N <= 2 000 000 000.

Входные данные
В первой строке находятся числа a₁ и N, разделённые пробелом.

Выходные данные
Вывести одно число - a_N.

Многоугольник на плоскости задан целочисленными координатами своих N вершин в декартовой системе координат. Требуется найти количество точек с целочисленными координатами, лежащих на границе многоугольника. Стороны многоугольника друг с другом не соприкасаются (за исключением соседних - в вершинах) и не пересекаются.

Ограничения: 3 <= N <= 100 000, координаты вершин целые и по модулю не превосходят 1 000 000 000.

Входные данные
В первой строке содержится число N, в следующих N строках - пары чисел - координаты точек. Если соединить точки в данном порядке, а также соединить первую и последнюю точки, получится заданный многоугольник.

Выходные данные
Вывести одно число - количество точек с целочисленными координатами на границе многоугольника.

Дано целое неотрицательное число в I-ричной системе счисления. Вывести это число в J-ричной системе счисления.

Входные данные
В первой строке находятся числа I и J (в десятичной системе счисления), во второй строке - число для перевода. 2 <= I, J <= 36, для представления цифр 10...35 используются прописные латинские буквы A...Z
 соответственно, число разрядов исходного числа не превышает 1000.

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

Даны целое неотрицательное число M и целое положительное число N. Найти M div N и M mod N.

Входные данные
В первой строке находится число M, во второй - N. 0 <= M <= 10⁶⁰⁰⁰⁰, 1 <= N <= 1 000 000.

Выходные данные
В первой строке вывести значение выражения M div N во второй - выражения M mod N.

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

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

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

Даны целые неотрицательные числа M и N. Найти M*N.

Входные данные
В первой строке находится число M, во второй - N. 0 <= M, N <= 10²⁵⁰⁰.

Выходные данные
Вывести одно число - результат умножения.