Distinct Subarray GCDs

Time limit5sMemory limit256 MB

Summary

Count the distinct GCD values taken over all contiguous subarrays for each test case.

Level: Medium5 of 10
Topics: Number theory, Dynamic programming, Hash map
Solved: No attempts yet

Problem

For a sequence $A$ of length $n$ , define $f(lo, hi)$ as the GCD of $A_{lo}$ through $A_{hi}$ (indices, not values). Count how many distinct values $f(lo, hi)$ can take.

Input

Multiple test cases. Each starts with $n$$(1 \le n \le 100000)$ , then $n$ lines each with an element $a$$(1 \le a \le 100)$ . Input ends when $n = 0$ .

Output

For each test case, print the number of distinct GCD values on one line.

Examples1

Example 1
Input
```
2
4
6
3
3
6
8
0
```
Expected output
```
3
5
```