Модульное возведение в степень дроби - PullRequest
Новая
       51

Модульное возведение в степень дроби

0 голосов
/ 03 апреля 2020

Модуляр рационального числа ie a / b, где a, b принадлежат множеству целых чисел, можно найти путем вычисления модульной обратной величины b.mod (m) = b -1 . Наконец, * b -1 mod (m) дает нам требуемый результат. Как мы можем найти модульное из (a / b) n эффективно? Учитывая, что n имеет порядок 1e9, существует ли эффективный метод для вычисления результата с учетом переполнения значений? Я попробовал что-то вроде этого, как показано ниже. 

const int modular = 1e9+7;


int modular_inverse(long long base) {
    long long result = 1;
    int power = modular-2;
    int MOD = modular;
    while(power > 0) {

        if(power & 1) {
            result = (result*base) % MOD;
        }
        base = (base * base) % MOD;
        power >>= 1;
    }
    return result;
}

int main() {
    int a = 27;
    int b = 2048;
    int A = a;
    int B = b;

    for(int i = 0; i < 1e9-1; ++i) {
        A *= a;
        B *= b;
        A = A%modular;
        B = B%modular;
    }
    int B_inv = modular_inverse(B);
    long long res = A*B_inv;
    res = res%mod;
    cout << res << endl;
}

1 Ответ

0 голосов
/ 03 апреля 2020

Вы можете рассчитать (ab -1 ) n mod (M) , используя быстрое возведение в степень

Примечание что вы на самом деле реализовали быстрое возведение в степень в функции modular_inverse, где вы вычисляете базу -1 мод (М) , которая равна базе М-2 mod (M) , если M - простое число.

Итак, вам нужно вычислить b -1 (что вы уже делаете), а затем вычислить (ab -1 ) mod (M), Затем возведите результат в степень n, используя быстрое возведение в степень, выполняя все операции по модулю M.

...