Блог

Сегодня я практиковался с головоломкой «быстрая мощность», в которой использовалась формула: (a * b) % p = (a % p * b % p) % p для вычисления (a^n)%p , что-то вроде этого: 2^31 % 3 = 2

Однако я так смущен, когда нашел ответ, используемый ((temp * temp) % b * a) % b; для решаемой ситуации, когда n нечетно, например 2^3

(temp (temp * temp) % b * a рекурсивно или (temp * temp) % b ).

Разве это не должно быть ((temp * temp) % b * a%b) % b ?

Поскольку в соответствии с этой формулой все должно %b быть до времени вместе.

Разве это не должно быть ((temp * temp) % b * a % b) % b ?

Нет. Поскольку a , если вы заранее знаете, что a это не будет переполняться (a меньше b), вам не нужно его модифицировать.

Идея заключается в том, что модульная арифметика работает для сложения и умножения. Операции типа (a b) % M = (a % M b % M) % M и (a * b) % M = (a % M * b % M) % M обычно выполняются, чтобы избежать переполнения (a * b) и (a b) и сохранить значение в определенном диапазоне.

Пример:

 const int Mod = 7;
int a = 13;
int b = 12;
int b = b % Mod; // b now contains 5 which is certainly smaller than Mod

int x = (a % Mod * b) % Mod; // you won't need to mod b again if you know beforehand b is smaller than Mod
 

Обновить

C реализация степенной функции:

 #define MOD 1000000007
// assuming x and n both be positive and initially smaller than Mod
int power(int x, int n) {
    if(n == 0) return x;
    int half = power(x, n / 2) % Mod;
    int ret = (half * half) % Mod; // you didn't need to do (half % Mod * half % Mod) % Mod because you already know half is smaller than Mod and won't overflow. 
                                   // Modulas being performed on the multiplied output, so now ret will be smaller than Mod
    if(n amp; 1) {
        ret = (ret * x) % Mod; // you didn't need to do (ret % Mod * x % Mod) % Mod
                               // because you already know ret and x is smaller than Mod
    }
    return ret;
}
 

Мод — это дорогостоящая операция. Поэтому вам следует избегать этого, когда это возможно.