Mô tả và yêu cầu

Vào thế kỷ trước một nhà toán học đã định nghĩa hàm 𝑓 trên dãy gồm 𝑁 số nguyên
dương 𝐴 = 𝑎1, 𝑎2, … ,𝑎𝑁 như sau: 𝑓(𝑖, 𝑗) = gcd(𝑎𝑖, 𝑎𝑖+1, … ,𝑎𝑗−1, 𝑎𝑗) với 1 ≤ 𝑖 ≤ 𝑗 ≤
𝑁, trong đó gcd(𝑎𝑖, 𝑎𝑖+1, … ,𝑎𝑗−1, 𝑎𝑗) là ước chung lớn nhất của các số
𝑎𝑖,𝑎𝑖+1, … ,𝑎𝑗−1, 𝑎𝑗.

Vài năm sau đó một nhà toán học khác áp dụng hàm 𝑓 trên dãy 1,1, … ,1 và nhận xét
rằng hàm 𝑓 luôn có giá trị bằng 1. Trên cơ sở đó ông ta đưa ra giả thiết là giá trị của
hàm 𝑓 luôn là một hằng số mà không phụ thuộc gì vào dãy 𝐴.

Yêu cầu: Với kiến thức toán học và lập trình của mình bạn hãy bác bỏ giả thiết trên
bằng cách chỉ ra hàm 𝑓 có thể có nhiều giá trị khác nhau trên dãy 𝐴 cho trước.

Dữ liệu vào: Từ tệp văn bản GTKN.INP gồm:

 Dòng 1 ghi số nguyên dương 𝑁;
 Dòng 2 ghi 𝑁 số nguyên dương 𝑎1, 𝑎2, … ,𝑎𝑁(1 ≤ 𝑎𝑖 ≤ 1018).

Kết quả: Ghi ra tệp văn bản GTKN.OUT gồm:

 Một dòng ghi một số là số giá trị khác nhau của hàm 𝑓 trên dãy 𝐴 đã cho.

Ví dụ 1:

GTKN.INP GTKN.OUT

4 6

9624

Ví dụ 2:

GTKN.INP GTKN.OUT

4 5

9634

Giới hạn và chấm điểm

 Có 40% số lượng test thỏa mãn 𝑁 ≤ 1000;
 Có 30% số lượng test thỏa mãn 𝑁 ≤ 5000;
 Có 30% số lượng test thỏa mãn 𝑁 ≤ 100000.