3

我需要计算第一个 n tetranacci 数字的总和,但我使用的公式

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

有一个部门。
我正在f(n) modulo 10^9 + 7计算第 n 个 tetranacci 项。在某些情况下,它给出了正确的答案,但不是全部。

有人可以帮我了解如何计算它的正确逻辑吗?

4

2 回答 2

2

对于模算术,用模逆代替乘法除法。

如果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 = 3m = 10^9 + 7,所以k = (10^9 + 8)/3 = 333333336

但是,如果n不是的倍数,则不起作用d

于 2012-06-30T09:15:03.690 回答
0

如果你的号码在一个数字数组中,你可以使用这个来计算这个大数字的 mod:

long mod_ans = 0;

for(i = 0; i < digits_array_length; i++)

{

    int digit = digits_array[i];
    mod_ans = (mod_ans * 16 + digit) % num;
}
于 2012-06-30T14:06:34.240 回答