Subarray GCD

View as PDF

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 128M

Author:
Problem types

Given an array of length , count the number of distinct greatest common divisors (GCDs) of all subarrays of this array.

We define the greatest common divisor of a subarray as the greatest common divisor of all the subarray's elements.

Input Specification

The first line of input will contain the integer , the length of the array .

The next line will contain space separated integers

Output Specification

One line, the number of distinct subarray GCDs.

No further restrictions.

Sample Input

3
1 6 4

Sample Output

4