Автор: cheops (06.12.2011 в 19:38)
3. На пальцах это вот что. Число a^m - очень большое и не убирается в базовом типе, поэтому его нужно либо хранить в строке, что медленно и требуется много памяти, либо вообще не вычислять, тем более оно нам не нужно, нам нужен a^m % m, т.е. узнать, будет ли это конечное число делиться без остатка на m или нет, а если будет, то какой будет остаток. Поэтому операция a^m разгалается на m отдельных операций a * a * a * ... * a. Цикл по этим итерациям реализован в виде рекурсии - вызова функции modpow() самой себя. Причем на каждой итерации мы не вычисляем значение a * a, а вычисляем какой будет остаток. Это позволяет оставаться в рамках базовых чисел не вылезая за границы числа.