algorithm - 找到给定音调和 987654321 的除法余数

Question

你能帮帮我吗？我需要一个快速算法来计算以下内容:给定范围(从 A 到 B ，1 < A,B < 10^8 ) 和 987654321; 例如，如果我有 A = 10，B = 15，我应该计算

((11^11) + (12^12) + (13^13) + (14^14) ) % 987654321

如果我使用这种直接方法，则需要很长时间才能计算出来。有计算这种余数的技巧吗？

Answer 1

使用快速模幂，我们可以在 O(log(n)) 时间内计算出 x^n。在最坏的情况下，如果 A = 1 and B = n 其中 n 可以达到 10^8，那么总的复杂度将约为

log(2) + log(3) + log(4) + ... + log(n)
= log(n!)
~ n*log(n) - n + O(log(n))  (According to Striling's Approximation)

Wikipedia

快速模幂运算

此方法用于快速计算 x^n 形式的幂(在 O(log(n)) 时间内)。

它可以作为递归关系给出:

x^n = (x^2)^(n/2)     if n is even
    = x*{(x^2)^(n/2)} if n is odd

因此，我们基本上不是乘以 x n 次，而是执行以下操作:

    x = x^2;
    n = n/2;

我们到达一个简单情况的时间，其中 n = 1。

Python 代码(在本例中带有模数):

def fast(x, n, mod):
    if n == 1:
        return x % mod
    if n % 2 == 0:
        return fast(x**2 % mod, n/2, mod)
    else:
        return x*fast(x**2 % mod, (n-1)/2, mod) % mod