В Python математический модуль содержит ряд математических операций, которые могут быть выполнены достаточно быстро. Встроенную функцию math.gcd(a, b), которая вычисляет НОД двух любых целых чисел. Можно использовать с версии 3.5.
math.gcd(a, b),
solve(A)
n
А
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач