FunnyScientist's blog

By FunnyScientist, 7 years ago, In English

I'm learning number theory and I cannot figure out the solution of following problem:

Given an array of integer A with N element with constrains N <= 10^5, A[i] <= 10^12. We call GCD(L, R) is greatest common divisor of all element A[L], A[L + 1], ..., A[R]. Return the sum of all contiguous sub-sequence in A.

I did have some idea that, for fixed index i, the value of GCD(i, j) will be decreasing as GCD(i, j) >= GCD(i, j + 1). Also, because GCD(i, j + 1) must be equal or divisor of GCD(i, j), the number of distinct value X of GCD(i, j), GCD(i, j + 1), ..., GCD(i, N) will satisfies 2^X <= A[i].

But I cannot go further. Please give me some more insights.

Read more »

  • Vote: I like it
  • +8
  • Vote: I do not like it