Проблема с модульным возведением в степень

Question

Я пытаюсь решить проблему, в которой мы должны вывести последний ди git с заданным числом n ^ p.

int modularExponentiation(int n, long long p, int m){
    if(p == 0) return 1;
    if(p & 1)
        return (n % m * modularExponentiation((n*n) % m, p / 2, m) % m) % m;//line 4
    return modularExponentiation((n*n) % m, p / 2, m) % m;
}

В этом рекурсивном коде мы здесь меняем временную результат по модулю в строке 4. Не приведет ли это к какому-либо изменению в окончательном ответе? например, если на каком-либо промежуточном этапе ответ будет 81 ^ 4, применяя% 10 к 81 и заменяя его на 1, не изменится ли он в конечном результате?

Answer 1

Нет, это не влияет на результат, потому что (a*b)%m == ((a%m) * (b%m))%m. Конечно, возведение в степень - это просто повторное умножение, поэтому применяется тот же принцип.

(81 ^ 4)% 10 достаточно мал, чтобы попробовать это вручную. Go вперед, выпиши это.

Answer 2

Для модульного сложения и умножения вы можете использовать мод на каждом шаге, и это не повлияет на результат. Фактически, именно так вы должны выполнять модульное возведение в степень, чтобы избежать переполнения. Следовательно, ваша последняя функция будет выглядеть так:

long long modExp(long long n, long long p, long long m) {
    if (p == 0) {
        // m could be 1 you never know
        return 1 % m;
    }
    n %= m;
    return (n * modExp(n, p - 1, m)) % m;
}