Given an array A of length n = 10^5. I have to find the sum of GCD of all subarrays of this array efficiently.
import math
def lgcd(a):
g = a[0]
for i in range(1,len(a)):
g = math.gcd(g,a[i])
return g
n = int(input())
A = list(map(int,input().split()))
ans = 0
for i in range(n):
for j in range(i,n):
ans+=lgcd(A[i:j+1])
print(ans)
The first thing that should be marked is that GCD(A[i-1 : j]) * d = GCD(A[i : j]) where d is natural number. So for the fixed subarray end, there will be some blocks with equal GCD, and there will be no more than *log n* blocks, since GCD in one block is the divisor of GCD of another block, and, therefore, is at least two times smaller.
So the next algorithm can be used: for all elements in array lets assume that they are last elements of the subarray, and then will find all blocks of equal GCDs and add to our total sum *block size \* block gcd*.
To fastly find blocks with equal GCD you can use a segment tree. To find a block you just need to find the longest subarray ending in fixed element, where gcd is smaller, then on your previously checked block.
This algorithm is O(*n \* log n \* log k*) where k is a maximal number in the array.
For A = [120 ,15 ,36, 20]
For 120 there is only one block - 120 (GCD(120) = 120). So Total sum is now 0 + 120 * 1 = 120
For 15 there is only one block of length two - 15 (GCD(15) = 15, GCD(120, 15) = 15). So the total sum is now 120 + 15 * 2 = 150.
For 36 there are two blocks - 36 (GCD(36) = 36) and 3 (GCD(15, 36) = GCD(120, 15, 36) = 3). So the total sum is now 192 = 150 + 36 * 1 + 3 * 2 = 192.
For 20 there are three blocks - 20 (GCD(20) = 20), 4 (GCD(36, 20) = 4) and 1 (GCD(15, 36, 20) = GCD(120, 15, 36, 20) = 1). So the total sum is now 102 + 20 * 1 + 4 * 1 + 1 * 2 = 218, and it is the answer
The efficient method is observing the problem statement closely. Example we have array as [1,2,3,45]. Now when we find GCD of [1,2] and we need to find GCD of [1,2,3] we can simply do it with GCD(GCD([1,2]),3). So here are overlapping subproblems. So just store the result.
A subarray of length k is constructed from subarray of length k-1 + 1 element. So GCD of subarray including k'th element is GCD of k'th element and GCD of subarray of k-1 elements i.e. GCD(GCD(A[i:i+k],A[k]).
final = dict()
def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)
A = [int(i) for i in input().split()]
dp = [[-1 for _ in range(len(A))] for _ in range(len(A))]
# Set GCD of single element as the elemnt itself
for i in range(len(A)):
dp[i][i] = A[i]
# For every other subarrays of length l
# Calculate gcd using length l - 1
for i in range(0, len(A)):
for j in range(i + 1, len(A)):
dp[i][j] = gcd(dp[i][j - 1], A[j])
final[tuple(A[i: j + 1])] = dp[i][j]
print(final)
