Problem E
GCDs
Given a sequence $A$ of $n$ numbers, define $f(lo,hi)$, $1 \le lo \le hi \le n$, as the Greatest Common Divisor of all the numbers $A_{lo}$ through $A_{hi}$, inclusive. Note that $lo$ and $hi$ are indices, not members of the list. Given an array, considering all possible values of $lo$ and $hi$, how many unique values of $f(lo,hi)$ will there be?
Input
There will be a single test case in the input. This test case will begin with a line with a single integer $n$ ($1 \le n \le 100\, 000$) representing the length of the sequence. The next $n$ lines will each have an integer $a$ ($1 \le a \le 100$). These are the numbers in the sequence, in sequence order.
Output
Output a single integer denoting the number of unique values $f(lo,hi)$ can have for the input sequence.
Sample Input 1 | Sample Output 1 |
---|---|
2 4 6 |
3 |
Sample Input 2 | Sample Output 2 |
---|---|
3 3 6 8 |
5 |