Codeforces Round 730 (Div. 2) |
---|
Закончено |
Добро пожаловать в Рокпорт-Сити!
Пришло время для вашей первой гонки в игре против Ронни. Чтобы сделать гонку интересной, вы поставили $$$a$$$ долларов, а Ронни — $$$b$$$ долларов. Но, похоже, фанаты разочарованы. Азарт фанатов равен $$$gcd(a,b)$$$, где $$$gcd(x, y)$$$ обозначает наибольший общий делитель (НОД) чисел $$$x$$$ и $$$y$$$. Чтобы сделать гонку более азартной, вы можете выполнять следующие операции:
За один шаг вы можете выполнить любую из этих операций. Вы можете сделать любое (в том числе ноль) число шагов. Определите максимальный азарт, который могут испытать фанаты, и минимальное число шагов, необходимое, чтобы его достичь.
Обратите внимание, что $$$gcd(x,0)=x$$$ для всех $$$x \ge 0$$$.
Первая строка содержит одно целое число $$$t$$$ ($$$1\leq t\leq 5\cdot 10^3$$$) — количество наборов входных данных.
Первая и единственная строка каждого набора входных данных содержит два целых числа $$$a$$$ и $$$b$$$ ($$$0\leq a, b\leq 10^{18}$$$).
Для каждого набора входных данных выведите строку, содержащую два целых числа.
Если фанаты могут испытать бесконечный азарт, выведите 0 0.
В противном случае первое число должно быть равно максимальному азарту, который фанаты могут испытать, а второе — минимальному количеству шагов, необходимому, чтобы достичь этот азарт.
4 8 5 1 2 4 4 3 9
3 1 1 0 0 0 6 3
В первом наборе входных данных вы можете проделать первую операцию $$$1$$$ раз, получив $$$a=9$$$ и $$$b=6$$$. Можно показать, что $$$3$$$ – максимальный возможный азарт.
Во втором наборе входных данных, независимо от операций, азарт фанатов будет равен $$$1$$$. Поскольку изначальный азарт так же равен $$$1$$$, вам не нужно проделывать никакие операции.
В третьем наборе входных данных фанаты могут испытать бесконечный азарт, применяя первую операцию бесконечное количество раз.
В четвертом наборе входных данных вы можете применить вторую операцию $$$3$$$ раза, получив $$$a=0$$$ и $$$b=6$$$. Поскольку $$$gcd(0,6)=6$$$, фанаты испытают азарт, равный $$$6$$$.
Название |
---|