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

На доске были выписаны два квадрата натуральных чисел: \(x^2\) и \(y^2\), где \(l \le y^2 < x^2 \le r\). Числа \(x^2\) и \(y^2\) стерли и выписали на доске их разность \(d\).

По заданным \(l\), \(r\) и \(d\) выясните, сколько различных пар натуральных чисел \(x^2, y^2\) могло быть выписано на доске.

Формат выходных данных
В первой строке даны три числа \(d\), \(l\) и \(r\) (\(1 \le d \le 10^9, 1 \le l \le r \le 10^{18}\)).

Формат входных данных
Выведите количество подходящих пар квадратов.

Примечание
В первом примере подходят числа 100 и 36. Во втором примере также подходят числа 256 и 196.

У Старца Летовца есть маленький прапраправнук по имени Летовёнок. Летовёнок очень любознательный и уже с ранних лет увлёкся математикой. Старец Летовец подарил ему набор чисел из натурального ряда, чтобы Летовёнок мог учиться считать. Но Летовёнок уже давно умеет считать и уже даже изучает делимость числа на три.

У Старца Летовца есть набор чисел. Эти числа можно склеивать друг с другом (или не склеивать вовсе), чтобы получать новые числа. Например, из набора чисел 12, 2 и 10 можно склеить число 12210, а можно 10212 — вариантов много, но выбрать придётся только один, потому что все числа в наборе в единственном виде.
Летовёнок задумался: какое максимальное количество чисел, делящихся на три, можно получить из этого набора?

Помогите ему решить эту задачу.

Формат входных данных

В первой строке ввода дано единственное число n (1<= n <=1000). Во второй строке ввода через пробел даны n чисел numi (1<=numi<=1000).

Формат выходных данных
Выведите одно число - максимальное количество чисел, кратных трём, которые можно получить из набора.


Примечание
В первом тестовом примере можно склеить числа 2 и 10 (получить 210 или 102) и в итоге получится 2 числа, кратные трём.

Во втором тестовом примере ничего склеивать не надо, так как. все числа уже кратны трём.

Старец Летовец, известный своими суперскиллами, решил научить своих учеников создавать "Последовательность Трёх Сил". Он дал им список чисел и сказал: "Отсортируйте эти числа так, чтобы они образовали Последовательность Трёх Сил. Вот правила:"

1. Сила Тройки. Числа, которые делятся на 3, должны идти первыми.

2. Сила Порядка. Среди чисел, делящихся на 3, меньшие числа должны идти перед большими.

3. Сила Простоты. Среди чисел, не делящихся на 3, числа имеющие большее количество делителей должны идти раньше, чем числа имеющие меньшее количество делителей. При равном числе делителей, числа должны идти в порядке убывания.

Напишите программу, которая реализует это правило, и создаёт Последовательность Трёх Сил из любого списка целых чисел.

Формат входных данных
В первой строке записано натуральное число n (n <= 10⁵) - количество целых чисел в списке. Далее, в n строках записано по одному целому числу numi ( -10⁵ <= numi <= -10⁵).


Формат выходных данных
Выведите в одной единственной строке Последовательность Трёх Сил, составленную из исходного списка чисел.

Дед мороз получил очень странное послание! Помогите ему. Напишите программу, которая выводит это сообщение в понятной форме 

–Т—Л–≤–µ–і–Є—В–µ –і–≤–∞–і—Ж–∞—В—М –њ–µ—А–≤—Л—Е –њ—А–Њ—Б—В—Л—Е —З–Є—Б–µ–ї
 

Муми-Тролли хотят украсить свою ёлку гирляндами, чтобы она светилась во время новогоднего праздника. Известно, что длина всех витков гирлянды, необходимых для полного обвивания ёлки, составляет L метров. Каждая гирлянда имеет длину M метров. Помогите муми-троллям посчитать сколько всего гирлянд необходимо муми-троллям?

Формат входных данных
В первой строке записано натуральное число L (L < 10⁹). Во второй строке - натуральное число M (M < 10⁹).

Формат выходных данных
Выведите одно число - количество необходимых гирлянд

Оргкомитет и жюри Московской олимпиады проводят очередные учебно-тренировочные сборы. Победители туров на сборах получают в качестве приза мороженое. Поскольку мороженое имеет тенденцию таять, то оно должно храниться в холодильнике. Холодильник, имеющийся в 179 школе слишком мал для хранения всего запаса мороженого. Поэтому организаторы решили заказать специальный супер-пупер-большой холодильник. Новый холодильник должен быть параллелепипедом A × B × C и хранить ровно N кубических баночек мороженого размером 1 × 1 × 1. Для уменьшения потерь холода, общая площадь поверхности холодильника должна быть как можно меньше.

Например, если размер холодильника должен быть 12, возможными вариантами являются:

 
 

Размеры баночек	Площадь поверхности
3 × 2 × 2	32
4 × 3 × 1	38
6 × 2 × 1	40
12 × 1 × 1	50

Лучшим вариантом является 3 × 2 × 2.

Помогите организаторам сборов выбрать оптимальную форму холодильника.

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

Входной файл содержит одно число N (1 ≤ N ≤ 10⁶).

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

Выведите три числа A, B и C — оптимальные длины сторон холодильника. Если решений несколько — выведите любое из них.

Фонд изучения дикой природы в течение \(t\) лет ежегодно выделяет денежные гранты в поддержку исследований северной фауны. На гранты претендуют три организации, одна из которых занимается изучением тюленей, вторая "— оленей, третья "— белых медведей.

Для упрощения бухгалтерского учёта фонд принял следующие решения:

В \(i\)-м году фонд планирует полностью распределить \(n_i\) денежных единиц, выделенных на гранты. Сравнивать результативность использования средств возможно только для грантов одинакового размера, выделенных каждой из трёх организаций. Такие гранты называются целевыми. Распределение денежных единиц на гранты между тремя организациям считается оптимальным, если как можно бОльшая часть общей суммы выделена на целевые гранты.

Например, если в текущем году на все гранты выделено 47 денежных единиц, то оптимальным вариантом распределения будет: выделить каждой из организаций целевые гранты размерами по 2 и 8 денежных единиц, что составит в сумме 30 единиц. Остальные 17 единиц можно распределить, например, выделив первой организации 16 денежных единиц, а третьей — 1 денежную единицу. Выделить более 30 денежных единиц на целевые гранты, распределяя 47 денежных единиц, нельзя.

Требуется написать программу, которая по заданной в \(i\)-м году общей сумме грантов \(n_i\) определяет, сколько денежных единиц следует выделить каждой из трёх организаций при оптимальном распределении грантов.

В первой строке входных данных записано целое число \(t\) — количество лет (\(1 \le t \le 100\)). В каждой из последующих \(t\) строк записано целое число \(n_i\)"— общая сумма грантов, которую необходимо полностью распределить в \(i\)-м году.

Выходные данные должны содержать \(t\) строк по три целых числа в каждой — суммы грантов, которые следует выделить каждой из трёх организаций в соответствующий год. Если оптимальных вариантов распределения несколько, необходимо вывести любой из них.

Дано натуральное число N. Требуется представить его в виде суммы двух натуральных чисел A и B таких, что НОД (наибольший общий делитель) чисел A и B — максимален.

Ограничение по времени выполнения программы - 1 секунда, ограничение по используемой памяти - 64 мегабайта.

Входные данные
Во входных данных записано натуральное число N (2 ≤ N ≤ 10⁹)

Выходные данные
Выведите два искомых числа A и B. Если решений несколько, выведите любое из них.

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

Входные данные
В первой строке задана цифра 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
 

По введенному натуральному числу K, не превосходящему 1 000 000, выдать K-ое по счету простое число.

Входные данные
Во входном файле находится одно натуральное число K.

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

Требуется заполнить 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.

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

Входные данные
Программа получает на вход строку, состоящую из цифр 0, ..., 9 и букв A, ..., F, являющуюся записью некоторого 16-ричного целого числа. Длина строки не превосходит 50 символов, первый символ в строке не равен 0. Необходимо вывести запись этого числа в двоичном виде без лидирующих нулей. 

Выходные данные
Выведите результат перевода.

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

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

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

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

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

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

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

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

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

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

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

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