Bài 11: Số ước chung - Tài liệu Tin học

Đăng bởi Admin

Tháng 10 8, 2022

https://chuyenhalong.ucode.vn/problems/so-uoc-chung-117903

Cho dãy $\mathrm{n}$ số nguyên dương $A=\left(a_1, a_2, \ldots, a_n\right)$ . Hãy đếm số lượng số nguyên dương $\mathrm{x}$ là ước số chung của tất cả các số trong dãy. Nói cách khác, bạn phải tìm số lượng các ước số chung của tất cả các phần từ trong dãy.

Ví dụ: Nếu dãy $A=(2,4,6,2,10)$ , thì các số 1 và 2 là ước của tất cả các phần tử trong dãy. Vì vậy câu trả lời cho trường hợp này là 2.

Đầu vào
– Dòng đầu tiên của đầu vào chứa số nguyên $\mathrm{T}(1 \leq T \leq 50$ ) là số bộ dữ liệu vào. Theo sau là các bộ dữ liệu vào, mỗi bộ dữ liệu vào gồm 2 dòng:
+ Dòng 1 chứa một số nguyên $\mathrm{n}\left(1 \leq n \leq 10^5\right)$ là số phần tử trong dãy $\mathrm{A}$ .
+ Dòng 2 chứa $\mathrm{n}$ số nguyên dương $a_1, a_2, \ldots, a_n\left(1 \leq a_i \leq 10^{12}\right)$ mô tả các phần tử của dãy $\mathrm{A}$ .
Các số cùng dòng cách nhau bởi dấu cách. Tổng các giá trị của $\mathrm{n}$ trong tất cả các bộ dữ liệu không quá $10^5$ .

Đầu ra
– Ứng với bộ dữ liệu vào, chương trình của bạn cần in ra một dòng chứa số nguyên dương $x$ là số lượng các ước số chung của tất cả các phần tử trong dãy $\mathrm{A}$ tương ứng.