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

Ввод	Вывод
1	7
0	7
35	70

 

Весь год Гошан был прилежным мальчиком и делал добрые дела: переводил бабушку через дорогу, еженедельно оставался в школе на контесты, давал одноклассникам списать химию и т.д.  За это Дедушка Мороз позволил Гошану выбрать абсолютно любой подарок на новый год. Гошан воспользовался возможностью и попросил долгожданную для него книгу “History of Hip-Hop”, ведь он был истинным поклонником хип-хопа! За кем же еще может стоять андерграунд?

Но Дед Мороз решил устроить испытание для мальчика. Он поставил на коробку с книгой кодовый замок.
Кодовый замок устроен следующим образом. На электронном экране замка появляются три числа – a , b и c. Чтобы открыть замок необходимо перевести числа a и b в двоичную систему счисления и поразрядно выполнить для них операцию c.
Описание операций:

1	Конъюнкция
2	Дизъюнкция
3	Исключающее или
4	Импликация
5	Эквивалентность

Результат операции необходимо представить в виде числа в двоичной системе счисления, а затем перевести в десятичное число .
Это число и будет являться ключом числа.
Помогите Гошану открыть замок, ведь с логикой у него плохи дела, а ему очень хочется поскорее почитать “History of Hip-Hop”.
P.S. Если в одном из чисел a и b разрядов будет больше, чем в другом, то в наименьшее необходимо добавить ведущие нули.
Входные данные
Входной файл содержит в себе три числа – a,b(1<=a,b<=1000) и с(1<=c<=5).
Выходные данные
Необходимо вывести одно число – ответ на задачу.
Пример
Ввод:
12 10 5
Вывод:
9
Пояснение
12=1100
10=1010
 
1100
1001
 
1001=9

(с) Курбатов Егор 9и

Какая система счисления используется в компьютерной технике?

1. двоичная
2. унарная
3. шестнадцатеричная
4. десятичная

Скоро в Соединенных Штатах Берляндии пройдут выборы президента. На эту ответственную должность претендуют два кандидата: Дядя Сэм и Дядя Фродо. Вы работаете аналитиком в пред- выборном штабе Дяди Сэма, и вам поручено помочь ему победить конкурента. Раздуть газетный скандал из одержимости оппонента бросанием колец в жерла вулканов не получилось, так что при- дётся воспользоваться математикой.

Казалось бы, чтобы выиграть, необходимо убедить проголосовать за нашего кандидата более половины пришедших на выборы. Оказывается, что иногда нужно гораздо меньше! Для того чтобы понять, как это возможно, рассмотрим подробнее процедуру голосования.

Как вы знаете, Соединенные Штаты Берляндии разделены на несколько административных ре- гионов первого уровня — штатов. Сначала в каждом из штатов проходят местные выборы, по итогам которых каждый штат отдаёт свой голос за одного из кандидатов. Если не менее половины штатов выбрало Дядю Сэма, то выигрывает он (в случае равенства голосов Дядя Сэм имеет преимущество как действующий президент), иначе побеждает Дядя Фродо. Все штаты, в свою очередь, состоят из административных регионов второго уровня, каждый из которых представлен выборщиком из административных регионов третьего уровня и так далее. Последний уровень состоит из отдельных жителей Берляндии. Всего в Берляндии N жителей и K уровней административных единиц. Одним из ключевых принципов этой страны является равенство, так что любой регион i-го уровня делится на одинаковое число регионов следущего уровня (в том числе содержит одинаковое число граждан).

Так получилось, что делением на регионы поручили заняться именно вам, то есть в ваших руках назначить, на сколько именно административных единиц i-го уровня делится (i−1)-ая администра- тивная единица.

Также у вас есть сильный инструмент влияния на выбор людей — нефтяные бурли. Чтобы заста- вить одного избирателя отдать свой голос за Дядю Сэма, достаточно дать ему скромный подарок в размере одного нефтяного бурля.

К несчастью, изначально все N жителей Соединённых Штатов Берляндии собираются отдать свой голос за Дядю Фродо. Требуется определить минимальное количество нефтяных бурлей, ко- торое достаточно потратить для победы на выборах.

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

В единственной строке ввода находятся два целых числа N и K (1 <= N <= 10¹⁵ , 1 <= K <= 10).

Формат выходных данных
Требуется вывести единственное число — минимальное количество нефтяных бурлей, которое придётся потратить на предвыборные подарки при наилучшем разбиении на регионы.

Примеры

Ввод	Вывод
9 2	4
12 3	2

Замечание
Берляндские законы не запрещают, чтобы страна состояла из одного штата, а город — одного жителя. Аналогично с остальными типами регионов.

На рисунке 1 черным цветом отмечены те регионы, в которых победил Дядя Сэм. На нижнем уровне черными изображены вершины, соответствущие подкупленным конкретным жителям.

Введите с клавиатуры целое число X (|X| ≤ 10⁹).
В первых трех строках выведите это число на экран в двоичной, восьмеричной, 16-ричной системах счисления.
В следующих двух строках выведите, поместится ли это число в ячейке типа byte и ячейке типа short ("YES"/"NO").
Запрещается использовать циклы и знания о том, сколько именно байт/бит памяти занимают переменные типа int, byte, short.
Пример ввода:

123

 
Пример вывода:

1111011 173 7B YES YES

 
Пример ввода:

40000

 
Пример вывода:

1001110001000000 116100 9C40 NO NO

Напишите функцию, вычисляющую количество делителей числа

Используя данную функцию, напишите программу, которая среди n натуральных чисел, вводимых с клавиатуры, выводит на экран число с максимальным количеством делителей
Входные данные:
в первой строке вводится число n - количестве чисел (n<=100),
далее идут n строк по одному натуральному числу в строке
Выходные данные:
программа должна вывести одно  число, в котором количество делителей максимально среди всех чисел, если таких чисел несколько, то необходимо вывести число, которое встретилось в последовательности раньше

Количество баллов за задачу уточняется после ручной проверки (и будет снижено, в случае если вы не используете функцию!).

Пример

Ввод	Вывод
5 22790 94 66 18 18	22790
2 21 46	21

Найти количество всех четырехзначных простых чисел, оканчивающиеся на цифру k.

Входные данные 
Число k.

Выходные данные 
Вывести число - количество простых чисел, удовлетворяющих условию задачи. Если таких чисел нет то вывести слово Absent.

Примеры

№	Входные данные	Выходные данные
1	1	266
2	0	Absent

Постулат Бертрана (теорема Бертрана-Чебышева, теорема Чебышева) гласит, что для любого \(n > 1\) найдется простое число p в интервале \(n < p < 2n\). Такая гипотеза была выдвинута в 1845 году французским математиком Джозефом Бертраном (проверившим ее до \(n=3000000\)) и доказана в 1850 году Пафнутием Чебышевым. Раманужан в 1920 году нашел более простое доказательство, а Эрдеш в 1932 – еще более простое.

Ваша задача состоит в том, чтобы решить несколько более общую задачу – а именно по числу n найти количество простых чисел p из интервала \(n < p < 2n\).

Напомним, что число называется простым, если оно делится только само на себя и на единицу

Входные данные
Целое число n (\(2 <= n <= 50000\)).

Выходные данные 
Выведите одно число – ответ на задачу.

 

Примеры

№	Входные данные	Выходные данные
1	3000	353

Дано натуральное десятичное число N (N<=255). Найдите местоположение младшего единичного бита. Выведите номер бита в десятичной системе счисления

Дано натуральное число N (N<=255). Найти сумму цифр данного числа в двоичной системе счисления. Ответ вывести в десятичной системе.

Дано натуральное число N (N<=255). Найти сумма цифр данного числа в восьмеричной системе счисления.

Дано натуральное число N . Необходимо найти максимальную цифру данного числа при его записи в восьмеричной системе счисления.

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

Выходные данные
Выведите на экран ответ на задачу.
 

 

Примеры

№	Входные данные	Выходные данные
1	255	7

 

Дано натуральное десятичное число N. Найдите количество единиц в двоичной записи данного числа. Ответ вывести в десятичной системе счисления.

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

Выходные данные
Выведите на экран ответ на задачу.
 

 

Пример

№	Входные данные	Выходные данные
1	100	3

 

В строке  записано натуральное число, не превышающее 10¹⁰⁰.
Нужно вывести результат уменьшения этого числа на 1.

В строке  записано натуральное число, не превышающая 10¹⁰⁰
Нужно вывести результат умножения этого числа на 2.

Для быстрого вычисления наибольшего общего делителя двух чисел используют алгоритм Евклида. Он построен на следующем соотношении: НОД(a,b)=НОД(a % b,b). Реализуйте рекурсивный алгоритм Евклида в виде функции gcd(a, b).

Ввод
12 16
Вывод
4

Даны два натуральных числа. Каждое из чисел не превышает 10¹⁰⁰.

Нужно вывести одно целое число — максимальное. Если они оба одинаковые, то выведите любое их них.

Процессор обрабатывает информацию:

1. в десятичной системе счисления
2. в двоичном коде
3. на языке Бейсик
4. в текстовом виде