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

По данному числу N распечатайте все целые степени двойки, не превосходящие N, в порядке возрастания. Операцией возведения в степень пользоваться нельзя!

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

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

Примеры

№	Входные данные	Выходные данные
1	30	1 2 4 8 16

Задано натуральное число N, не превышающее 10⁸ . Требуется определить, сколько чётных цифр входит в его запись в троичной системе счисления.
Входные данные
число N, записанное в десятичной системе счисления.
Выходные данные
количество чётных цифр, входящих в запись числа N в троичной системе счисления.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4	0	410=113
2	15	2	1510=1203

Дана последовательность из N чисел. Рассматриваются все её непрерывные подпоследовательности, которые содержат кратное K количество отрицательных чисел, заканчивающихся цифрой m. Найдите среди них подпоследовательность с максимальной суммой.  Программа должна вывести одно число – максимальную сумму элементов такой подпоследовательности. Гарантируется, что в исходной последовательности существует хотя бы K отрицательных чисел, заканчивающихся цифрой m.


Входные данные
В первой строке программа получается три числа: количество чисел в последовательности N (100 <= N <= 5000000), натуральное число K и натуральное число m (0 <= m <= 9). В каждой из следующих N строк записано одно целое число, не превышающее по модулю 10000. Гарантируется, что сумма любой подпоследовательности исходной последовательности не превышает по модулю 10⁹.

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1

 

На вход программе подается последовательность целых чисел.  Рассматриваются все непрерывные подпоследовательности исходной последовательности, сумма элементов которых кратна K. Найдите количество таких подпоследовательностей. Гарантируется, что в последовательности такая подпоследовательность есть.

Входные данные
В первой строке записаны натуральные числа N (1 <= N <= 10⁸) и K (1 <= K <= 100 ). Каждая из следующих N строк содержит одно натуральное число, не превышающих 10000.

Выходные данные
Выведите на экран одно число – количество таких подпоследовательностей. 

Примеры

№	Входные данные	Выходные данные
1	5 3 33 41 19 22 40	4

N коров (1 ≤ N ≤ 10⁵) Фермера Джона стоят в ряд. i-ая корова слева имеет метку i (1 ≤ i ≤ N).
ФД дал коровам M пар целых чисел s (L₁,R₁)…(L_M,R_M), где 1 ≤ M ≤ 100. Затем он сказал коровам повторить ровно K (1 ≤ K ≤ 10⁹) раз процесс из M шагов:

Для каждого i от 1 до M:
Последовательность коров на позициях Li…Ri слева реверсивно меняют свой порядок.
Выведите метки всех коров слева направо для каждого i, (1 ≤ i ≤ N) после завершения описанного процесса.

Входные данные
Первая строка содержит числа N, M, K. Для каждого 1 ≤ i ≤ M строка i+1 содержит L_i и R_i, два целых числа в интервале 1…N, где L_i<R_i.

Выходные данные
На i-ой строке вывода, выведите i-ый элемент массива после выполнения всех инструкций K раз.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	7 2 2 2 5 3 7	1 2 4 3 5 7 6	Изначально порядок коров слева направо такой     [1,2,3,4,5,6,7]  После первого шага процесса порядок станет таким [1,5,4,3,2,6,7] После второго шага процесса порядок станет таким [1,5,7,6,2,3,4].  Повторив оба шага ещё раз получим результат, приведенный в выводе.

Дана последовательность из N натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, такие что сумма элементов каждой из них кратна K. Найдите среди них подпоследовательность с максимальной суммой, определите её длину. Если таких подпоследовательностей найдено несколько, в ответе укажите количество элементов самой короткой из них.

Входные данные
В первой строке записаны натуральные числа N (1 <= N <= 10⁸) и K (1 <= K <= 100 ). Каждая из следующих N строк содержит одно натуральное число, не превышающих 10000.

Выходные данные
Выведите на экран одно число - количество элементов самой короткой подпоследовательности с максимальной суммой элементов кратной К.
 
 

Примеры

№	Входные данные	Выходные данные
1	7 43 21 13 9 19 17 26 95	2

В этом наборе можно выбрать последовательности 21+13+9 (сумма 43) и 17+26 (сумма 43). Самая короткая из них, 17 + 26, имеет длину 2. Для указанных программа должна вывести число 2.

Дана последовательность из N чисел. Найдите минимальную сумму всех элементов собственного префикса последовательности, у которого сумма всех элементов префикса при делении на K имеет тот же остаток, что и сумма всех элементов данной последовательности.  Если таких префиксов несколько определите тот, у которого меньше длина. Выведите на экран длину такого префикса. Гарантируется, что такой префикс существует.


Входные данные
В первой строке записаны два числа: количество чисел в последовательности N (1 <= N <= 10⁸) и число K (1 <= K <= 100). Далее идет N строк, по одному целому числу в строке. Каждое число не превышает 10000.

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

Примеры

№	Входные данные	Выходные данные
1	5 2 2 -2 2 -2 2	2

 

 

Дана последовательность из N натуральных чисел. Найдите максимальную сумму всех элементов собственного префикса последовательности, у которого сумма всех элементов префикса при делении на K имеет тот же остаток, что и сумма всех элементов данной последовательности. Гарантируется, что такой префикс существует.


Входные данные
В первой строке записаны два числа: количество чисел в последовательности N (1 <= N <= 10⁸) и число K (1 <= K <= 100). Далее идет N строк, по одному натуральному числу в строке. Каждое число не превышает 10000.

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

Примеры

№	Входные данные	Выходные данные
1	5 3 33 41 18 23 40	92

 
 

Дана последовательность из N натуральных чисел. Найдите минимальную длину собственного префикса последовательности, у которого сумма всех элементов префикса при делении на K имеет тот же остаток, что и сумма всех элементов данной последовательности. Гарантируется, что такой префикс существует.

Входные данные
В первой строке записаны два числа: количество чисел в последовательности N (1 <= N <= 10⁸) и число K (1 <= K <= 100). Далее идет N строк, по одному натуральному числу в строке. Каждое число не превышает 10000.

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

Примеры

№	Входные данные	Выходные данные
1	5 3 33 41 18 23 40	2

 

 

Дана последовательность из N натуральных чисел. Найдите максимальную длину собственного префикса последовательности, у которого сумма всех элементов префикса при делении на K имеет тот же остаток, что и сумма всех элементов данной последовательности. Гарантируется, что такой префикс существует.


Входные данные
В первой строке записаны два числа: количество чисел в последовательности N (1 <= N <= 10⁸) и число K (1 <= K <= 100). Далее идет N строк, по одному натуральному числу в строке. Каждое число не превышает 10000.

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

Примеры

№	Входные данные	Выходные данные
1	5 3 33 41 19 22 40	2

 
 

Дана последовательность из N натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, начинающиеся с первого элемента последовательности. Найдите максимальную длину подпоследовательности с суммой элементов кратной K. Длина подпоследовательности равна числу элементов в ней.

Входные данные
В первой строке записаны два числа: количество чисел в последовательности N (1 <= N <= 10⁸) и число K (1 <= K <= 100). Далее идет N строк, по одному натуральному числу в строке. Каждое число не превышает 10000.

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

Примеры

№	Входные данные	Выходные данные
1	5 3 33 41 19 22 40	3

Громозека и Алиса старые друзья. Встречаясь на какой-то планете, они постоянно заходят в кафе. Но Алиса не любит заходить в каждое a-ое кафе, а Громозека в каждое g-ое кафе. Чтобы никого не обидеть, они не заходят в те кафе, в которые не хотят заходить одновременно и Алиса и Громозека. На очередной прогулке у них на пути N кафе. Во сколько кафе они смогут зайти?

Входные данные
Единственная строка содержит три целых числа - a , g , N ( 1 <= a , g , N <= 10⁹ ).

Выходные данные
Выведите единственное число - количество кафе, в которые смогут зайти Громозека и Алиса.
 

Примеры

№	Входные данные	Выходные данные
1	1 1 10	0
2	1 2 5	3

Среди чисел от 1 до N определите сколько чисел с максимальным количеством четных цифр в системе счисления с основанием r. Четными цифрами в любой системе счисления будем считать цифры 0, 2, 4, 6, 8.

Входные данные
Программа получает на вход 2 числа: N (1< N <= 10⁵) и r (2 <= r <= 9).

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

Примеры

№	Входные данные	Выходные данные
1	5 4	2

Наибольшим общим делителем непустого набора натуральных чисел A называется максимальное натуральное число d, такое что оно является одновременно делителем всех чисел множества A.
Задан массив натуральных чисел [a₁, a₂, . . . , a_n] и число k. Требуется выбрать в нем подмассив из k подряд идущих элементов [a_l, a_l+1, . . . , a_l+k−1], чтобы их наибольший общий делитель был как можно больше, и вывести этот наибольший общий делитель.

Входные данные
Первая строка ввода содержит два целых числа n и k (2 ≤ n ≤ 500 000, 2 ≤ k ≤ n).
Вторая строка содержит n натуральных чисел a₁, a₂, . . . , a_n (1 ≤ a_i ≤ 10¹⁸).

Выходные данные
Выведите одно натуральное число — максимальное возможное значение наибольшего общего делителя элементов подмассива длины k заданного массива.

Примеры

№	Входные данные	Выходные данные
1	10 4 2 3 4 8 12 6 12 18 4 3	6

Марья Ивановна с Марьей Михайловной привели школьников в кинотеатр. Чтобы не было никаких обид, Марья Ивановна построила всех школьников по алфавиту и рассадила их: сначала в первый ряд слева направо, затем во второй слева направо и т.д., заполнив весь зал из n рядов по m кресел. Тут пришла Марья Михайловна и сказала, что ребята сели неправильно – надо пересесть. Она предложила сначала заполнить все первые места от первого ряда к последнему, затем все вторые места и т. д.

Определите, сколько школьников после такой пересадки останется на своем месте.

Например, если n = 3 и m = 3, то в первом случае дети сядут так:

1    2    3
4    5    6
7    8    9
а во втором – так:
1    4    7
2    5    8
3    6    9
Таким образом, три школьника: 1, 5 и 9 останутся на своих местах.

Входные данные
Вводятся два целых числа n и m (1 ≤ n, m ≤ 10⁹ ).

Выходные данные
Выведите количество школьников, которые останутся на своих местах.
 

Примеры

№	Входные данные	Выходные данные
1	3 3	3
2	2 4	2

Значение выражения \( 27^7 - 3^{11} + 36 - x\) записали в троичной системе счисления, при этом сумма цифр в записи оказалась равной b (вводится с клавиатуры, 0 < b < 100).  Напишите программу, которая выводит на экран минимальное натуральное значение x. Гарантируется, что ответ существует.

Результат арифметического выражения \(9^9 – 3^9 + 9^{19} – 19 \) записали в троичной системе счисления. Напишите программу, которая определит количество цифр "2", "1" и "0"в результирующем числе. Выведите ответ в одной строке, через пробел, в указанном порядке.

У Анны Николаевны есть N ящиков с конфетами. В i-м ящике лежит Ai количество конфет.  Анна Николаевна достает конфеты из нескольких последовательных коробок и равномерно раздает их M детям. Найдите количество пар (l, r), удовлетворяющих следующим условиям:
- l и r целые числа и удовлетворяют условию 1<=l<=r<=N;
- Al + Al+1 + ... + Ar делится на M.

Входные данные
Программа получает на вход две строки. Первая строка содержит два целых числа N (1<=N<=10⁵) и M (2<=M<=10⁹). Вторая строка содержит N чисел Ai (1<=A_i<=10⁹, 1<=i<=N).

Выходные данные
Выведите количество пар (l, r), удовлетворяющих условиям. Обратите внимание, что число может не соответствовать 32-битному целочисленному типу.
 

Примеры

№	Входные данные	Выходные данные
1	3 2 4 1 5	3
2	13 17 29 7 5 7 9 51 7 13 8 55 42 9 81	6

Подсчитайте количество натуральных делителей числа x (включая 1 и само число x).

Входные данные
Вводится натуральное число x (x < 30000).

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

Примеры

№	Входные данные	Выходные данные
1	32	6

Выведите все натуральные делители числа x в порядке возрастания (включая 1 и само число).

Входные данные
Вводится натуральное число x

Выходные данные
Выведите все делители числа x

 

Примеры

№	Входные данные	Выходные данные
1	32	1 2 4 8 16 32