sum of the GCD of all the subarrays

[notacoder]

what is the most efficient way to find the sum of gcds of all the subarray without using tabular DP(as the memory constraints doesn't allow to form 2D array)

[jonnin]

what does all subarray mean here? every combination?

[notacoder]

Subarray means continuous subsequence

[Ganado]

So just to be clear on the terminology, if the array as a whole is [2, 4, 6], you must skip gcd(2, 6)?

I'm sure websites like geeksforgeeks have had this question done dozens of times, so you could just search for it, it sounds like a code competition question.

[ne555]

> memory constraints doesn't allow to form 2D array
if the idea is to create a matrix where G[j][k] = gcd(v[j]...v[k]) then you need to notice that it will have a lot of repeated elements
so you may compress that information and it will not exceed the memory limit

[jonnin]

gcd probably has properties that help. there is likely something like gcd (2,4) and gcd(2,4,6) that you can do to save work, to find the second one faster using knowledge of the first one.. these things are math problems first, coding second, go do the math.

[ne555]

some properties

gcd(a,b,c) = gcd(gcd(a,b), c)
gcd(a, b) <= min(a,b)
gcd(a, 1) = 1

[notacoder]

@ne555 can you explain how to compress the dp array?

[lastchance]

#include <iostream>
#include <vector>
using namespace std;

//================================================

int gcd( int a, int b )
{
   return b ? gcd( b, a % b ) : a;
}

//================================================

int sumAll( const vector<int> A )
{
   int N = A.size();
   vector<int> B = A;
   int sum = 0;

   for ( int i : B ) sum += i;                   // subsequences of length 1

   for ( int Lm1 = 1; Lm1 < N; Lm1++ )           // subsequences of length 2, ..., N
   {                                             //      Lm1 is length minus 1
      int sumlast = sum;
      for ( int i = 0; i + Lm1 < N; i++ )        // replace element B[i] with
      {                                          //      gcd( A[i], ..., A[i+Lm1] )
         if ( B[i] != 1 ) B[i] = gcd( B[i], A[i+Lm1] );
         sum += B[i];
      }

      if ( sum - sumlast == N - Lm1 )            // shortcut exit once all B[i] are 1
      {
         int triangle = N - Lm1 - 1;
         if ( triangle > 0 ) sum += triangle * ( triangle + 1 ) / 2;
         break;
      }
   }
   return sum;
}

//================================================

int main()
{
   vector<int> A = { 6, 18, 12, 36, 5 };
   cout << sumAll( A );
}

[ne555]

for example https://en.wikipedia.org/wiki/Run-length_encoding
also, because of symmetry, you may just work on the lower triangle

GCD[0] = {v[0], 1}
for K in range(1,n):
	GCD[K] = compress({gcd(GCD[K-1], v[K]), {v[K], 1}})

so we store pairs {value, count}
we'll fill the lower triangle, so at each step, compute the gcd between each element of the previous row and the current v_k
then in compress(), just check for contiguous elements that have the same value and sum their count.

[notacoder]

@ne555
Can you write the code implementation of the above explanation for an example

[ne555]

def compress(array):
	result = {array[0]}
	for K in range(1, len(array)):
		if array[K].value == array[K-1].value: //same element, update the count
			result.back().count += array[K].count
		else: //new element, insert it
			result.append(array[K])
	return result

[dutch]

notacoder wrote:

Can you write the code implementation of the above explanation for an example

Can you do anything yourself?