对于大型输入而言，使该程序的运行速度更快

Question

def calculate(i,j,m,k,n):
    for v in range(1,n+1):
        ans = (i*k + j) % m
        k = ans
    return ans

程序代表一个通用公式，其中 x = (i * k + j) % m其中 k是上一个答案的值。从某种意义上说，它基本上是x1 = (i * x0 + j) % m和x2 = (i * x1 + j) % m，依此类推。我遇到的问题是计算大型输入需要很长时间。

考虑到这一点，我正在考虑使用算术系列公式(例如： a + (n - 1) * d)(的线条，但我不确定如何在这样的程序中实现它。

Answer 1

x1 = (i * x0 + j)
x2 = (i * x1 + j) = i * i * x0 + i * j + j
x3 = i * i * i * x0 + i * i * j + i * j + j
xn = i^n * x0 + sum(i^t for t from 0 to n - 1) * j
   = i^n * x0 + (i^n - 1) / (i - 1) * j

找到了Wolfram Alpha的最后一行。

如果m是素数，则公式很好。在这种情况下，您可以执行所有计算模型，包括该部门，以使数字保持较小。您只需要快速获取i^n的启用即可。我建议您查看https://en.wikipedia.org/wiki/modular_exponentiation#right-to-to-left_binary_method及其中的参考。与环路的O( n (相比，这应该给您O(log( n ((时间复杂。

如果m不是素数，则上述公式中的划分很烦人。但是，您也可以通过平方计算总和来执行类似于指示的事情。观察

1 + i + i^2 + i^3 + i^4 + i^5 + i^6 + … + i^(2n+1) =
(1 + i) * (1 + i^2 + i^4 + i^6 + … + i^n)
1 + i + i^2 + i^3 + i^4 + i^5 + i^6 + … + i^(2n+2) =
1 + (i + i^2) * (1 + i^2 + i^4 + i^6 + … + i^n)

因此，您可以在每个步骤中右括号中的汇总数量一半。现在没有划分，因此您可以在每个操作后执行Modulo操作。因此，您可以定义

之类的东西

def modpowsum(a, n, m):
  """(1 + a + a^2 + a^3 + ... + a^n) mod m"""
  if n == 0:
    return 1
  if n == 1:
    return (1 + a) % m
  if n % 2 == 1:
    return ((1 + a) * modpowsum((a * a) % m, (n - 1) // 2, m)) % m
  return (1 + ((a + a * a) % m) * modpowsum((a * a) % m, n // 2 - 1, m)) % m

可以在https://ideone.com/xh0fuf上查看整个计算，运行了一些随机的，并且一些不太适用的测试用例。