For a research project, Rafid needs the sum of GCD values across every possible contiguous subarray of a large dataset. Given N integers, compute the sum of GCD(a[l..r]) over ALL O(N^2) subarrays, in O(N log(maxA)) using the fact that GCD values along a fixed left endpoint change O(log(maxA)) times as the right endpoint grows.
Input
Line1: N. Line2: N integers.
Output
Sum of GCD over all subarrays.
Constraints
1 ≤ N ≤ 10^5, 1 ≤ a_i ≤ 10^9
Sample Input
3 2 4 6
Sample Output
2+2+2+4+2+6=18
main.c
Loading editor…
Write C, then Run (custom I/O) or Submit (sample tests). ⌘/Ctrl+Enter submits.