算法 - 阶乘的除法求模 - 费马小定理

做完这道题感觉自己离散数学和算法真是白学了。。

例如:如何快速求 10000!/(4999! + 5000!) % 10^9 + 7 (m: 10000!, a: 4999! + 5000!, p: 10^9 + 7

首先根据费马下定理 (a ^ (p - 1)) % p = 1 (p 为素数) -> m * (a ^ (p - 2)) % p = (m / a) % p(p 为素数)

然后如何求a ^ (p - 2)?p 是非常大的数直接循环效率很差,可以求平方法快速求幂(如:求 a^2^2^2,只用三次求平方运行就相当于求 8 次方)将效率提高到O(log(p))

上一篇:使用Python进行*数据搜索


下一篇:如何使用Python抓取类别Wikipedia页面类别中的子类别和页面