c - （a / b）多数のmod n？

Question

最初のn個のテトラナッチ数の合計を計算する必要がありますが、使用している式は

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

関係する部門があります。
私はf(n) modulo 10^9 + 7n番目のテトラナッチ項を計算するためにやっています。場合によっては、正しい答えが得られますが、すべてではありません。

誰かが私がそれを計算する方法について正しい論理を得るのを手伝ってくれますか？

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 + 7k = (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;
}