分数的模幂

Question

有理数的模，即 a/b 其中 a,b 属于整数集，可以通过计算 mod 的 b.mod(m) = b^-1。最后 a*b^-1mod(m) 给了我们需要的结果。我们如何才能有效地找到 (a/b)ⁿ 的 modular？给定 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;
}

Answer 1

可以计算(ab^-1)ⁿmod(M) 使用 fast exponentiation

请注意，您实际上在计算基数^-1mod(M)[的modular_inverse函数中实现了快速取幂等于 base^M-2mod(M) 如果 M 是素数。

所以你需要计算b^-1（你已经做了），然后计算(ab^-1)mod(男)。然后使用快速求幂将结果提高到 n 次方，执行所有操作 modulo M.

分数的模幂

Modular exponentiation of a fraction

c++

modular