#1637. ƯỚC CHUNG (GCD)

Khi giảng dạy về nội dung ước số chung lớn nhất, Alice đã cho học sinh bài toán sau:

Cho số nguyên dương . Hãy chọn ra nhiều số nhất mà ước chung lớn nhất của chúng lớn hơn 1.

Ví dụ, với dãy số gồm bốn số , có thể chọn được nhiều nhất ba số là vì chúng có ước chung lớn nhất là 4 (lớn hơn 1).

Yêu cầu: Cho số nguyên dương . Hãy tính số lượng số nhiều nhất chọn được thỏa mãn điều kiện bài toán.

Dữ liệu:

• Dòng đầu chứa số nguyên dương ();
• Dòng thứ hai chứa số nguyên dương ().

Kết quả:

• Ghi ra một số nguyên là số lượng số chọn được.

Ví dụ:

Dữ liệu:

4
4 5 8 20

Kết quả:

3

Dữ liệu:

4
2 4 6 8

Kết quả:

4

Giới hạn:

• Subtask 1 (20%): và ().
• Subtask 2 (30%): .
• Subtask 3 (30%): ().
• Subtask 4 (20%): Không có ràng buộc nào thêm.