(a/b) 큰 숫자의 경우 mod n입니까?

Question

제가 처음 n tetranacci 번호의 합하지만

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

관여 분할을 가지고 사용하고있는 식을 계산할 필요가있다.
n 번째 tetranacci 항을 계산하려면 f(n) modulo 10^9 + 7을하고 있습니다. 경우에 따라 올바른 대답을 제공하지만 모든 사람에게 해당되는 것은 아닙니다.

누군가가 계산 방법에 대한 올바른 논리를 얻도록 도와 줄 수 있습니까?

Answer 1

모듈 식 산술에 대해서는 모듈러 인버스를 곱하여 나눗셈을 대체하십시오.

k*d ≡ 1 (mod m) 및 n 경우 따라서 (n/d)*(f*m)이 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 ≡ ((n % m)*k % m) (mod m) 

, d의 배수 , 그래서

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; 
}