(а / б) мод н для больших чисел?

Question

Мне нужно вычислить сумму первых n чисел тетраначчи, но формулу, которую я использую

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

имеет разделение вовлечено.
я делаю f(n) modulo 10^9 + 7 рассчитать n-й член тетраначи В некоторых случаях это дает правильный ответ, но не для всех.

Может кто-нибудь, пожалуйста, помогите мне получить правильную логику о том, как рассчитать это?

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

Если у вас есть ваш номер в массиве цифр, вы можете рассчитать мод для этого большого числа, используя это:

long mod_ans = 0;

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

{

    int digit = digits_array[i];
    mod_ans = (mod_ans * 16 + digit) % num;
}