Python中的模幂运算-yiteyi-C++库

给定三个数字x，y和p，计算（x^y）%p

null

例如：

Input:  x = 2, y = 3, p = 5
Output: 3
Explanation: 2^3 % 5 = 8 % 5 = 3.

Input:  x = 2, y = 5, p = 13
Output: 6
Explanation: 2^5 % 13 = 32 % 13 = 6.

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

上述解决方案的问题是，n或x的大值可能会发生溢出。因此，功率通常在大数模下计算。

朴素乘法是O（n），常数因子非常低，为%m。战俘函数在python中以O（logn）时间计算，但如果首先计算x的值，当数字足够大时，需要花费大量时间 ^Y 然后用p修改它，得到（x） ^Y )已评估%p。

                     # Simple python code that first calls pow()                   
                     # then applies % operator.                   
                     a                               =                               2                   
                     b                               =                               100                   
                     p                               =                               (                               int                               )(                               1e9                               +                               7                               )                   
                             
                     # pow function used with %                   
                     d                               =                               pow                               (a, b)                               %                               p                   
                     print                               (d)                   

输出：

976371285

当使用大数模进行计算时，%运算符需要花费大量时间，因此使用了快速模幂运算。Python已经 战俘（x，e，m） 要计算模，所需时间要少得多。[请参考 Python文档详细信息]

                     # Fast python code that first calls pow()                   
                     # then applies % operator                   
                     a                               =                               2                   
                     b                               =                               100                   
                     p                               =                               (                               int                               )(                               1e9                               +                               7                               )                   
                             
                     # Using direct fast method to compute                   
                     # (a ^ b) % p.                   
                     d                               =                               pow                               (a, b, p)                   
                     print                               (d)                   

输出：

976371285

中对快速模幂算法进行了更简要的解释链接

文章版权归作者所有，未经允许请勿转载。

THE END

Python