function gcd(x, y){
while(y)
[x, y] = [y, x % y];
return x;
}
function f(A){
const memo = {};
const n = A.length;
const mid = n / 2;
function g(l0, l1, r0, r1){
const key = String([l0, l1, r0, r1]);
if (memo.hasOwnProperty(key))
return memo[key];
const len_l = l1 - l0 + 1;
const len_r = r1 - r0 + 1;
if (len_l + len_r == 2){
if (len_r && len_l)
return gcd(A[l0], A[r0]);
else if (len_l)
return gcd(A[l0], A[l0 + 1]);
else
return gcd(A[r0], A[r0 + 1]);
}
let a = A[l0];
let b = A[r1];
const outer = gcd(a, b) + g(l0 + 1, l1, r0, r1 - 1);
if (len_r >= len_l)
var mid = r0 + (len_l + len_r) / 2 - len_l;
else
var mid = l0 + (len_l + len_r) / 2;
b = A[mid];
const _l1 = l1 - (mid == l1 ? 1 : 0);
const _r0 = r0 + (mid == r0 ? 1 : 0);
const left = gcd(a, b) + g(l0 + 1, _l1, _r0, r1);
a = A[r1];
const right = gcd(b, a) + g(l0, _l1, _r0, r1 - 1);
return memo[key] = Math.min(outer, left, right);
}
return g(0, mid - 1, mid, n - 1);
}
let A = [2, 4, 8, 6];
console.log(JSON.stringify(A));
console.log(f(A));
A = [8,5,21,10,25,9]
console.log(JSON.stringify(A));
console.log(f(A));
const n = 200;
A = [];
for (let i=0; i<n; i++)
A.push(i + 1);
console.log(JSON.stringify(A));
console.log(f(A));