从 m 到 n 斐波那契数中找到总和的最后一位。 (0 ≤ ≤ ≤ 10^14)

Question

我的代码如下：

m, n = map(int, input().split())

# write function "fibtotal" which takes input x and gives accurate fib(x+2)%10  (as sum till fib(x) == fib(x+2) - 1)
# using above function get fibtotal(m-1) and fibtotal(n)
# subtract fibtotal(m-1) from fibtotal(n) and do mod 10 gives last digit of sum from m to n
# take care of handling large input sizes, 0 ≤  ≤  ≤ 10^14

def fibtotal(x):

  sum = 1 # if both initial conditions fail then loop starts from 2

  x= x % 60 # pisano period of 10 is 60 and to get last digit we need to divide by 10

  if x == 0:
    sum = 1 # fib(2)
    return sum 

  if x == 1:
    sum = 2 # fib(3)
    return sum

  a, b = 0, 1

  for i in range(2, x+3): # to find sum till fib(x+2)

    c = (a+b)%10
    sum += c
    a, b = b%10, c%10

  return sum%10

# no need to subtract 1 from both as they cancel out
print(fibtotal(n)-fibtotal(m-1))

以下案例使用此算法失败：

10 10 我的输出：4，正确输出：5

10 200 我的输出：5，正确输出：2

1234 12345 我的输出：2，正确输出：8

（可能还有更多）

我想知道问题出在哪里，如何解决？使用相同的基本原理是否有更好的方法？

Answer 1

循环次数有问题：你在应该有x的地方循环了x+1次。我不明白你为什么不以 sum = 0.

开头

然后，你可以利用周期在恒定时间内计算总和，无需任何循环。 aux 列表是使用 fibtotal1.

计算的

def fib(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b
    return a

def fibtotal1(n):
    return sum(fib(k) % 10 for k in range(n + 1)) % 10

def fibtotal2(n):
    s, a, b = 0, 0, 1
    for i in range(n % 60):
        a, b = b, a + b
        s += a
    return s % 10

aux = [0, 1, 2, 4, 7, 2, 0, 3, 4, 8, 3, 2, 6, 9, 6, 6, 3, 0, 4, 5,
       0, 6, 7, 4, 2, 7, 0, 8, 9, 8, 8, 7, 6, 4, 1, 6, 8, 5, 4, 0,
       5, 6, 2, 9, 2, 2, 5, 8, 4, 3, 8, 2, 1, 4, 6, 1, 8, 0, 9, 0]

def fibtotal3(n):
    return aux[n % 60]

print(all(fibtotal1(n) == fibtotal2(n) == fibtotal3(n) for n in range(1000)))

另请注意，在您的最后一步中，由于计算 mod 10，差异可能为负，因此应为：

def fibtotal(m, n):
    return (fibtotal3(n) - fibtotal3(m - 1)) % 10

对于经过的reader：fibtotal2和fibtotal3有效，因为fib(n) % 10是周期性的，周期为60，周期元素的总和是10 的倍数。参见 Math.SE 上的 Fibonacci's final digits cycle every 60 numbers。

Answer 2

正如让-克洛德上面提到的，主要有两个错误

no. of times the loop run

理想情况下，循环应该运行 x 次（包括条件），但我将其与 sum(fib(0 to x)) = fib(x+2) -1 混淆并使其成为运行x+2次

needless %10 at many places

唯一需要 mod 10 的地方是显示最终结果时的最后一条语句。这个错误的原因是过于关注处理大的输入大小，但它们已经被处理 x%60.

相同的修正代码如下所示：

m, n = map(int, input().split())


def fibtotal(x):

  sum = 1 # if both initial conditions fail then loop starts from 2

  x= x % 60 # pisano period of 10 is 60 and to get last digit we need to divide by 10

  if x == 0:
    sum = 1 # fib(2)
    return sum 

  if x == 1:
    sum = 2 # fib(3)
    return sum

  a, b = 0, 1

  for i in range(2, x+1): # to find sum till fib(x+2)

    c = a+b
    sum += c
    a, b = b, c

  return sum

# no need to subtract 1 from both as they cancel out
print((fibtotal(n)-fibtotal(m-1))%10)

注意：如果 m > 1，值 "sum" 并不重要，因为它在最后减去时抵消了

从 m 到 n 斐波那契数中找到总和的最后一位。 (0 ≤ ≤ ≤ 10^14)

Finding last digit of sum from m to n Fibonacci numbers. (0 ≤ ≤ ≤ 10^14)

python

algorithm

fibonacci

fibonacci-heap