--->
45 задач
<---
Источники
В марсианских сутках \(N\) часов. У марсиан Ятеп и Ашам есть часы со стрелками, которые работают почти так же, как земные – большая стрелка делает один оборот в час, а маленькая – один оборот в сутки. Ятеп и Ашам поссорились и решили не разговаривать, пока стрелки часов не совпадут. Определите точный момент времени, когда это случится.
Во входном файле задано число тестов \(K\) (0 ≤ \(K\)<\(10^4\)), далее для каждого теста указаны целые числа \(N\), \(A\), \(B\) и \(C\) (1<\(10^9\), 0 ≤ \(A\), 0 ≤ \(B\) < \(10^9\)). Числа \(A\), \(B\) и \(C\) означают, что Ятеп и Ашам поссорились в \(A\)+\(B\)/\(C\) часов.
Для каждого теста выведите искомое время в том же формате: числа \(A\), \(B\) и \(C\), такие, что искомое время равно \(A\)+\(B\)/\(C\) (0 ≤ \(A\), 0 ≤ \(B\), дробь \(B\)/\(C\) – несократимая).
2 12 11 0 1 12 0 0 1
0 0 1 1 1 11
На клетчатой бумаге Петя нарисовал отрезок из точки с координатами (\(a\),\(b\)) в точку с координатами (\(c\),\(d\)). Через сколько клеток проходит этот отрезок (считается, что отрезок проходит через клетку, если он проходит через ее внутренность, если же он проходит только через вершину или по границе клетки, считается, что он не проходит через клетку).
Вводятся целые числа \(a\), \(b\), \(c\), \(d\). Числа по модулю не превышают \(10^9\).
Выведите одно число — количество клеток, через которые проходит отрезок.
0 0 6 4
8
3 3 -3 3
0
Напишите функцию для нахождения наибольшего общего делителя двух чисел с помощью алгоритма Евклида и используйте ее в программе для нахождения НОД уже \(n\) чисел.
На вход программе сначала подается значение \(n\) (\(2 \le n \le 100\)). В следующей строке находятся \(n\) целых неотрицательных чисел, не превосходящих \(30\,000\).
Выведите НОД исходных чисел.
3 24 8 20
4
4 0 2 4 8
2
Напишите свой аналог функции fractions.gcd (назовите ее gcd).
Вводятся два натуральных числа через пробел.
Вывести их наибольший общий делитель.
928456982736495876239876592387469578236500 216498237659872365987387562938749785625
125
Натуральное число \(a\) называется делителем натурального числа \(b\), если \(b = ac\) для некоторого натурального числа \(c\). Например, делителями числа 6 являются числа 1, 2, 3 и 6. Два числа называются взаимно простыми, если у них нет общих делителей кроме 1. Например, 16 и 27 взаимно просты, а 18 и 24 — нет.
Будем называть нормальным набор из \(k\) чисел (\(a_1, a_2, \ldots, a_k\)), если выполнены следующие условия:
Например, набор (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