TLE-oj Cup Round 2 - GCD phân biệt - TLEOJ: TLE Online Judge

TLE-oj Cup Round 2 - GCD phân biệt

Điểm: 1600 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 128M

Input: GCDDIF.inp

Output: GCDDIF.out

Tác giả:

Sunlight

Dạng bài

Bạn được cho một dãy số nguyên dương $a_1$ , $a_2$ , $...$ , $a_n$ . Xét các cặp $(i, j)$ với $1 \le i \le j \le n$ , đặt $g$ là ước chung lớn nhất của $a_i$ , $a_{i + 1}$ , $...$ , $a_j$ . Hỏi có thể tạo ra bao nhiêu giá trị $g$ khác nhau khi xét tất cả các cặp $(i, j)$ .

Input, Output và Subtasks

Input (GCDDIF.inp)

Dòng đầu tiên là một số nguyên dương $n \le 10^5$ - số phần tử của dãy.
Dòng tiếp theo gồm $n$ phần tử $a_1$ , $a_2$ , $...$ , $a_n$ , $1 \le a_i \le 10^{18}$ .

Output (GCDDIF.out)

Một dòng duy nhất gồm kết quả bài toán - số giá trị $g$ phân biệt có thể tạo được.

Subtasks

Subtask 1 $(20\%)$ : $n \le 100$ .
Subtask 2 $(20\%)$ : $n \le 1000$ .
Subtask 3 $(30\%)$ : $n \le 5000$ .
Subtask 4 $(30\%)$ : $n \le 10^5$ .

Sample

Input (GCDDIF.inp)

4
9 6 2 4

Output (GCDDIF.out)

Notes

Các giá trị $g$ có thể tạo được là: $9, 6, 2, 4, 3, 1$ .

Bình luận

Không có bình luận nào.