相关疑难解决方法(0)

我很好奇是否有一个很好的方法来做到这一点.我目前的代码是这样的:

def factorialMod(n, modulus):
    ans=1
    for i in range(1,n+1):
        ans = ans * i % modulus    
    return ans % modulus

但它似乎很慢!

我也无法计算n!然后应用素数模数,因为有时n是如此之大,以至于n!明确计算是不可行的.

我也遇到过http://en.wikipedia.org/wiki/Stirling%27s_approximation,想知道这是否可以在某种程度上使用？

或者,我如何在C++中创建一个递归的,memoized函数？

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

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

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

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