CF664A Complicated GCD

Greatest common divisor $ GCD(a,b) $ of two positive integers $ a $ and $ b $ is equal to the biggest integer $ d $ such that both integers $ a $ and $ b $ are divisible by $ d $ . There are many efficient algorithms to find greatest common divisor $ GCD(a,b) $ , for example, Euclid algorithm. Formally, find the biggest integer $ d $ , such that all integers $ a,a+1,a+2,...,b $ are divisible by $ d $ . To make the problem even more complicated we allow $ a $ and $ b $ to be up to googol, $ 10^{100} $ — such number do not fit even in 64-bit integer type!

N/A

N/A