Наибольший общий делитель НОД(a, b) двух положительных целых чисел a и b равняется самому большому целому числу, на которое без остатка делятся оба числа a и b. Известны эффективные алгоритмы для нахождения НОД(a, b), например, алгоритм Эвклида. Усложним требования и будем просить решить более сложную задачу — нужно найти НОД среди всех чисел от a до b включительно.
Формально, найдите максимальное целое число, на которое без остатка делится каждое из чисел a, a + 1, a + 2, ..., b. Чтобы было бы ещё сложнее, разрешим a и b достигать числа гугол, 10100 — такие числа не помещаются даже в 64-битный тип целых чисел!
Выходные данные
Выведите одно число — НОД всех чисел от a до b включительно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 2
|
1
|
|
2
|
61803398874989484820458683436563811772030917980576 61803398874989484820458683436563811772030917980576
|
61803398874989484820458683436563811772030917980576
|