- 场景:很大的数的全排列,除以另外几个很大的数的全排列。对结果取很大的素数的模。
- 题目:Maximum Palindromes | HackerRank
- 费马小定理:Fermat's little theorem - Wikipedia
- 求平方法快速求幂:Exponentiation by squaring - Wikipedia
做完这道题感觉自己离散数学和算法真是白学了。。
例如:如何快速求 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))