将数字提高到巨大的指数 [英] Raising a number to a huge exponent

问题描述

给我数字3和一个变量'n'，该变量可以高达1000000000000(十亿).我必须打印3^n modulo 100003的答案.我尝试了以下方法:

I am given the number 3 and a variable 'n', that can be as high as 1 000 000 000 (a billion). I have to print the answer of 3^n modulo 100003. I tried the following:

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

3. 最后，我尝试对数字'n'进行质因子分解，然后使用'n'因子(及其出现的次数)来建立答案，这似乎是我可能会想到的最好方法(如果正确的话).问题是我要对已经是质数很大的数字怎么办?

1. I tried using the function std::pow(3,n), but it doesn't work for large exponents(can't apply the modulo during the process).
2. I tried implementing my own function that would raise the number 3 to the power n so I could apply the modulo when needed, but when tested with very large numbers, this method proved to be too slow.

3. Lastly I tried prime factorization of the number 'n' and then using the factors of 'n' (and how many times they appear) to build back the answer and this seems like the best method that I could come up with (if it is correct). The problem is what would I do for a huge number that is already prime?

这些就是我的想法，如果有人认为有更好的方法(或者如果我的方法之一是最佳方法)，我将不胜感激.

So these were the ideas that I had, if anyone thinks there's a better way (or if one of my methods is optimal), I would appreciate any guidance.

推荐答案

利用模块化算术的属性

(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

通过分治法计算结果.重复关系将为:

Calculate the result by divide and conquer approach. The recurrence relation will be:

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);
}

这篇关于将数字提高到巨大的指数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！