Темы --> Информатика --> Алгоритмы --> Арифметические алгоритмы
    НОД и алгоритм Евклида(45 задач)
    Системы счисления(36 задач)
    "Длинная" арифметика(58 задач)
    Простые числа и разложение на множители(45 задач)
    Остатки(21 задач)
    Быстрое возведение в степень(3 задач)
    Быстрое преобразование Фурье(3 задач)
---> 240 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 30 31 32 33 34 35 36 >> Отображать по:
#3368
Следующий!
  

Отсортируем все числа 0 до N включительно по количеству единиц в двоичном представлении. Таким образом, \(4=100_2\) идет раньше чем \(3=11_2\), так как в двоичном представлении имеет на одну единицу меньше. В случае одинакового количества единиц раньше идет то число, которое меньше.

Пример сортировки для N=7: 0,1,2,4,3,5,6,7.

Даны числа N и K. Требуется найти следующее после K в указанном выше порядке.

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

В первой строке входного файла содержится число \(N\) (\(1 \leq N \leq 10^{100}\)). Вторая строка содержит число \(K\) (\(0 \leq K \leq N\)).

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

В выходной файл выведите следующее за K число. В случае, если K - последнее число, то выведите -1.

Примеры
Входные данные
10
4
Выходные данные
8
Входные данные
12
11
Выходные данные
-1
#3374
Последовательность
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Известны первые \(k\) членов последовательности – \(a_1, a_2, \dots, a_k\) (\(0 \leq a_i \leq 9\), где \(i = 1, 2, \dots, k\)). Другие члены последовательности вычисляются по следующему правилу: \(a_i = \sum_{j=i-k}^{i-1}a_j\), то есть каждый следующий член равен сумме \(k\) предыдущих. Необходимо найти последние \(r\) цифр числа \(a_n\).

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

В первой строке входного файла находятся \(3\) целых числа – \(k\), \(n\) и \(r\) (\(1 \leq k \leq 20\), \(1 \leq n \leq 10^{18}\), \(1 \leq r \leq 9\)). В следующей строке находится \(k\) чисел – \(a_1, a_2, \dots, a_k\).

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

Первой строкой выходного файла выведите \(r\) цифр числа \(a_n\). Ведущие нули следует опустить.

Примечание

1. Тесты, в которых \(r = 1\), будут оцениваться 75 баллами:
1.1 Тесты, в которых \(n<10^6\), будут оцениваться 25 баллами.
1.2 Тесты, в которых \(n \geq 10^6\), будут оцениваться 50 баллами:
1.2.1 Тесты, в которых \(k < 7\), будут оцениваться 30 баллами.
1.2.2 Тесты, в которых \(6 < k < 11\), будут оцениваться 20 баллами.
2. Тесты, в которых \(r > 1\), будут оцениваться 25 баллами.

Примеры
Входные данные
2 5 1
1 2
Выходные данные
8
Входные данные
1 100001 1
5
Выходные данные
5
#3375
Размер команды
  
Темы: [Остатки]
ограничение по времени на тест
0.1 second;
ограничение по памяти на тест
64 megabytes

После объявления “проходных баллов” на всероссийскую олимпиаду по информатике, один большой начальник позвонил одному из руководителей команды г. Москвы, чтобы узнать, сколько же школьников поедет на олимпиаду по информатике и сколько будут стоить авиабилеты для всей команды. Чтобы не пугать большого начальника, руководитель команды не стал называть конкретное число, а уклончиво ответил, что количество школьников в команде дает остаток 1 при делении на 2, 3, 4, 5 и 6. Но поскольку большой начальник был математиком, то, зная, что школьников в команде не меньше 10 и не больше 100, он сразу же догадался, что в команде ровно 61 школьник.

Вам известны остатки от деления некоторого числа N на числа 2, 3, ..., K. Найдите наименьшее натуральное N, которое обладает таким свойством.

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

Первая строка входного файла содержит натуральное число K (2≤K≤20). Дальше идет K-1 строка, содержащая остатки от деления некоторого натурального числа N на числа 2, 3, ..., K.

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

Выведите наименьшее натуральное число N, обладающее таким свойством.

Примеры
Входные данные
6
1
1
1
1
1
Выходные данные
1
#3382
Корень
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

В этой задаче вам надо найти все корни \(k\)-ой степени из числа \(x\). Единственная проблема - это надо сделать по простому модулю \(p\). Другими словами, найдите все такие числа \(0 < y < p\), что \(y^k ~mod ~p = x\).

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

В единственной строке входного файла записаны \(3\) целых числа - \(p\), \(x\) и \(k\) (\(3 \leq p \leq 10^9\), \(0 < x < p\), \(1 \leq k \leq min(20,p-1)\), \(p\) простое).

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

В первой строке выведите количество различных корней \(m\). Во второй выведите \(m\) различных целых чисел в порядке возрастания - корни из \(x\). Обратите внимание на то, что корней может не быть (в этом случае вторая строка должна остаться пустой).

Примеры
Входные данные
43 25 2
Выходные данные
2
5 38
Входные данные
43 26 2
Выходные данные
0
#3383
Король
  
Быстрое преобразование Фурье

В некотором царстве жил-был король. У него была дочка – принцесса невиданной красоты. И настала пора её замуж отдать. В богатом королевстве неподалеку жил принц. И собрался король отвести принцессу, да не знает, какой маршрут выбрать. На тех землях ещё издревле было множество дорог – горизонтальных и вертикальных, и образовывали они клетчатую сетку на земле той. На перекрёстках располагались города. Город принцессы имеет координаты \((0, 0)\), а принца – \((n, m)\), уравнения дорог имеют вид \(x = x_0\) или \(y = y_0\), где \(x_0\), \(y_0\) целые. Король хочет проехать по как можно меньшему числу дорог, потому что он грабителей боится да вернуться хочет поскорей. Вам, как придворному математику, нужно посчитать, сколькими способами это можно сделать.

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

Во входном файле заданы неотрицательные целые числа \(n\) и \(m\), не превосходящие 400000.

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

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

Примеры
Входные данные
7 7
Выходные данные
3432
Входные данные
4 1
Выходные данные
5
Страница: << 30 31 32 33 34 35 36 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест