Блуждающий зуб
Две шестерни сцеплены: у первой a зубьев, у второй b. Пометим краской один зуб первой шестерни и одну впадину второй, в которую он сейчас вошёл. Через сколько полных оборотов каждой шестерни эта пара встретится снова?
Инженеры любят, когда числа зубьев взаимно просты: тогда каждый зуб первой шестерни со временем побывает в каждой впадине второй, и износ распределится равномерно. Такую передачу называют передачей с «блуждающим зубом». Для каждой пары шестерён определите и это.
Вход
В первой строке число пар q (1 ≤ q ≤ 100 000). В каждой из следующих q строк — a и b (1 ≤ a, b ≤ 10¹⁸).
Выход
Для каждой пары строку из четырёх значений: наибольший общий делитель a и b; сколько оборотов сделает первая шестерня до новой встречи пары; сколько — вторая; yes, если передача с блуждающим зубом, иначе no.
Примеры
Пример 1
5 40 15 41 15 12 12 1 7 89 55
5 3 8 no 1 15 41 yes 12 1 1 no 1 7 1 yes 1 55 89 yes
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 6 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
За один оборот первой шестерни мимо точки зацепления проходят a зубьев. Пара встретится снова, когда через зацепление пройдёт число зубьев, кратное и a, и b. Какое наименьшее такое число?
2Идея
Нужное число зубьев — наименьшее общее кратное: НОК(a, b) = a·b / НОД(a, b). Первая шестерня сделает НОК / a = b / НОД оборотов, вторая — a / НОД. Передача с блуждающим зубом — это НОД = 1: тогда первая шестерня успевает сделать полные b оборотов, и её зуб побывает во всех b впадинах.
3Разбор
Считаем НОД алгоритмом Евклида с делением с остатком и делим на него оба числа. Само НОК вычислять не нужно, и это удачно: при a, b до 10¹⁸ оно доходит до 10³⁶ и в Go не поместится ни в какой целый тип. Ответ — частные b/НОД и a/НОД, они не больше 10¹⁸.
В Go для чисел до 10¹⁸ хватает uint64 (и даже int64): остатки только уменьшаются, переполнению неоткуда взяться.
3+Решение
4Сложность
Не больше 85 делений на пару (худший случай до 10¹⁸ — соседние числа Фибоначчи, они в третьем тесте), всего O(q log max(a, b)).
5Типичные ошибки
- Вычитание вместо деления. Евклид в «Началах» вычитал меньшее из большего. На паре (10¹⁸, 1) это 10¹⁸ вычитаний — второй тест.
- НОК через произведение.
a * b / gв Go переполняется задолго до 10¹⁸ × 10¹⁸. Делите первым:a / g * b— а здесь НОК и вовсе не нужен. - Перепутанные обороты. Первая шестерня делает b/НОД оборотов, а не a/НОД: шестерня с меньшим числом зубьев крутится чаще.