（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的倍數，但是不起作用。

Answer 2

如果你有你在一個數字序列號，就可以計算出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; 
}