将数字提升到一个巨大的指数

Question

我得到数字3和变量'n',可以高达1 000 000 000(十亿).我必须打印答案3^n modulo 100003.我尝试了以下方法:

1. 我尝试使用该函数std::pow(3,n),但它不适用于大型指数(在此过程中无法应用模数).
2. 我尝试实现我自己的函数,将数字3提高到幂n,这样我就可以在需要时应用模数,但是当测试数量非常大时,这种方法被证明太慢了.

3. 最后,我尝试对数字'n'进行素数分解,然后使用'n'因子(以及它们出现的次数)来构建答案,这似乎是我能提出的最佳方法(如果是正确).问题是我会为已经素数很大的数字做些什么？

   所以这些是我的想法,如果有人认为有更好的方法(或者我的方法之一是最优的),我将不胜感激任何指导.

Answer 1

利用模运算的特性

(a × b) modulo M == ((a module M) × (b modulo M)) modulo M

通过使用上面的乘法规则

(a^n) modulo M 
= (a × a × a × a ... × a) modulo M 
= ((a module M) × (a modulo M) × (a modulo M) ... × (a modulo M)) modulo M

通过分而治之的方法计算结果.递归关系将是:

f(x, n) = 0                     if n == 0

f(x, n) = (f(x, n / 2))^2       if n is even
f(x, n) = (f(x, n / 2))^2 * x   if n is odd

这是C++实现:

int powerUtil(int base, int exp, int mod) {
    if(exp == 0) return 1;
    int ret = powerUtil(base, exp / 2, mod) % mod;
    ret = 1LL * ret * ret % mod;
    if(exp & 1) {
        ret = 1LL * ret * base % mod;
    }
    return ret;
}

double power(int base, int exp, int mod) {
    if(exp < 0) {
        if(base == 0) return DBL_MAX; // undefined
        return 1 / (double) powerUtil(base, -exp, mod);
    }
    return powerUtil(base, exp, mod);
}