Задача Фибоначчи, превышающая максимальное значение int - PullRequest
Новая
       37

Задача Фибоначчи, превышающая максимальное значение int

2 голосов
/ 15 марта 2020

Я пытаюсь решить https://www.spoj.com/problems/FIBOSUM/ проблему. 

MOD = 1000000007;

function copy(a, b) {
    a[0][0] = b[0][0];
    a[0][1] = b[0][1];
    a[1][0] = b[1][0];
    a[1][1] = b[1][1];
 }

function multiply(fib, base) {
    let mat = [[], []];
    copy(mat, fib);

    mat[0][0] = (fib[0][0]*base[0][0] + fib[0][1]*base[1][0]) % MOD;
    mat[0][1] = (fib[1][0]*base[0][0] + fib[1][1]*base[1][0]) % MOD;
    mat[1][0] = (fib[0][0]*base[0][1] + fib[0][1]*base[1][1]) % MOD;
    mat[1][1] = (fib[1][0]*base[0][1] + fib[1][1]*base[1][1]) % MOD;
    copy(fib, mat);
}

function calcMatrix(fib, n) {
    const base = [[1,1], [1,0]];
    fib[0][0] = 1;
    fib[0][1] = 0;
    fib[1][0] = 0;
    fib[1][1] = 1;

while (n) {
    print(n);
    if (n&1) {
        multiply(fib, base);
    }
    multiply(base, base);
    print('bef', n)
    n = n.toString(2).slice(0, -1); //same as n = n >> 1;
    print('aft', n)
    }
}

let t = parseInt(readline());
while(t--)
{
[N, M] = readline().split(' ');
N = Number(N);
M = Number(M);
let fib = [[],[]];
calcMatrix(fib, N);
let fn = fib[0][1];
let fn1 = fib[1][1] ;

calcMatrix(fib, M-N+2);
// (a%mod -b%mod +mod)%mod
let sum =  ((fib[0][0]-1)*fn + (fib[0][1]-1)*fn1 + MOD) % MOD;
print('wyni', sum);
}

Есть мое решение https://ideone.com/25HLU7. Для n = 78 результат правильный, более высокие значения дают результат, превышающий max int. Я не могу использовать BigInt () из-за spidermonkey.

...