title: How to find sum of all the GCDs of all the subarrays of an array?
body: <p>Given an array A of length n = 10^5. I have to find the sum of GCD of all subarrays of this array efficiently.</p>
  
  <pre><code>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)
  </code></pre>