Страница: << 1 2 3 Отображать по:
#3208
Делители
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Натуральное число \(a\) называется делителем натурального числа \(b\), если \(b = ac\) для некоторого натурального числа \(c\). Например, делителями числа 6 являются числа 1, 2, 3 и 6. Два числа называются взаимно простыми, если у них нет общих делителей кроме 1. Например, 16 и 27 взаимно просты, а 18 и 24 — нет.

Будем называть нормальным набор из \(k\) чисел (\(a_1, a_2, \ldots, a_k\)), если выполнены следующие условия:

  1. каждое из чисел \(a_i\) является делителем числа \(n\);
  2. выполняется неравенство \(a_1 \lt a_2 \lt \ldots \lt a_k\);
  3. числа \(a_i\) и \(a_{i+1}\) для всех \(i\) от \(1\) до \(k - 1\) являются взаимно простыми;
  4. произведение \(a_1a_2\ldots a_k\) не превышает \(n\).

Например, набор (2, 9, 10) является нормальным набором из 3 делителей числа 360.

Требуется написать программу, которая по заданным значениям \(n\) и \(k\) определяет количество нормальных наборов из \(k\) делителей числа \(n\).

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

Первая строка входного файла содержит два целых числа: \(n\) и \(k\) (\(2 \le n \le 10^8\), \(2 \le k \le 10\)).

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

В выходном файле должно содержаться одно число — количество нормальных наборов из \(k\) делителей числа \(n\).

Примечание

Правильные решения для тестов, в которых \(n \le 1000\) и \(k = 2\), оцениваются из 30 баллов.

Правильные решения для тестов, в которых \(k = 2\), оцениваются из 60 баллов (в эти баллы включаются также 30 баллов для случая \(n \le 1000\), \(k = 2\)).

Примеры
Входные данные
90 3
Выходные данные
16
Входные данные
10 2
Выходные данные
4
#112101
Паровозик из Морошково (BC)
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

Построенная пандорианцами железная дорога представляет собой прямой отрезок, проходящий в непосредственной близости от N красивейших водопадов. Паровозик, который планируется запустить по этой дороге, будет без остановок проезжать весь маршрут, преодолевая участки между водопадами за строго определённое время.

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

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

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

В первой строке через пробел вводятся два натуральных числа: количество часов в одних сутках ( H ) и минут в одном часу ( M ) на Пандоре ( 1 ≤ H , M ≤ 500 ).

Следующая строка содержит четыре целых числа, описывающих время начала ( H s , M s ) и конца ( H f , M f ) светового дня ( 0 ≤ H s , H f < H ; 0 ≤ M s , M f < M ). При этом либо H s < H f , либо H s = H f и M s < M f (гарантируется, что день начинается раньше, чем заканчивается). Если паровозик проезжает мимо водопада ровно в H s часов M s минут или ровно в H f часов M f минут, то считается, что он проехал мимо водопада днём.

Третья строка содержит одно натуральное число N — количество водопадов, рядом с которыми проезжает паровозик ( 1 ≤ N ≤ 100 000 ).

В следующих N - 1 строках вводятся по 2 целых числа H i и M i , описывающих продолжительность временных интервалов для проезда между соседними водопадами: H 1 , M 1 — время в пути между первым и вторым водопадами, H 2 , M 2 — между вторым и третьим и так далее. Гарантируется, что время, затрачиваемое на дорогу между любыми двумя соседними водопадами, строго положительно, не превосходит одних пандорианских суток и записано корректно: 0 ≤ H i ≤ H , 0 ≤ M i < M .

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

Если составить подходящее расписание невозможно, то в качестве ответа выведите одно слово « Impossible » (без кавычек). Иначе выведите два числа H 0 и M 0 , разделённые пробелом, описывающие любое подходящее время проезда паровозика рядом с первым водопадом.

Примечание

Тесты к этой задаче состоят из четырех групп.

  • Тесты 1–2. Тесты из условия, оцениваемые в ноль баллов.

  • Тесты 3–17. В тестах этой группы H = 24 , M = 60 и N ≤ 1000 . Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.

  • Тесты 18–38. В тестах этой группы H ≤ 80 , M ≤ 100 , N ≤ 100000 . Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.

  • В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 40 баллов. Решение будет тестироваться на тестах этой группы offline, т. е. после окончания тура. Тесты в этой группе оцениваются независимо.

Тестирование на тестах каждой группы производится только в случае прохождения всех тестов из всех предыдущих групп.

Примеры
Входные данные
24 60
8 0 22 0
6
6 0
21 0
19 0
12 0
10 0
Выходные данные
12 0
Входные данные
24 60
8 17 20 10
2
11 59
Выходные данные
Impossible
Страница: << 1 2 3 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест