c - (a/b) mod n 用于大数？

Question

我需要计算前 n 个 tetranacci 数字的总和，但我使用的公式是

sn = (f(n+2)+2*f(n)+f(n-1)-1)/3  

有一个部门参与。
我正在做 f(n) modulo 10^9 + 7 来计算第 n 个 tetranacci 项。对于某些情况，它会给出正确答案，但并非对所有情况都如此。

有人可以帮我找到正确的计算逻辑吗？

Answer 1

对于模运算，用模逆乘法代替除法。

如果k*d ≡ 1 (mod m)和 n是 d 的倍数, 然后

n/d ≡ ((n % m)*k % m) (mod m)

你可以看到

k = (f*m + 1)/d
n*k = (n*(f*m + 1))/d = ((n*f)*m + n)/d = (n/d)*(f*m) + (n/d)

现在，n/d假设是一个整数，因此 (n/d)*(f*m)是 m 的倍数, 所以

n*k ≡ n/d (mod m)

从那以后

n*k ≡ (n % m)*k (mod m)

命题如下。

在这种情况下，d = 3和 m = 10^9 + 7 , 所以 k = (10^9 + 8)/3 = 333333336 .

如果n 不是 d 的倍数，但这不起作用。