#1390. MGCD - Tích ước chung lớn nhất

Bộ nhớ: 256 MiB Thời gian: 500 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Chùm CUỐI

Đề bài

NGUỒN: Bài tập Bồi dưỡng HSGQG, Hải Phòng, T11/2020, Thái BK

Cho dãy A gồm n số nguyên dương: a_1, a_2, …, a_n . Hãy tính:

\prod\nolimits_{S \subset A}^{S \ne \emptyset } {\gcd (S)}

trong đó gcd(S) là số nguyên dương lớn nhất là ước của tất cả các số trong S

Dữ liệu vào:

  • Dòng đầu tiên chứa n ;
  • Dòng tiếp theo chứa n số nguyên dương là dãy A .

Dữ liệu ra:

  • Một số nguyên là kết quả bài toán sau khi chia lấy dư cho 10^9 + 7 .

Ví dụ:

Dữ liệu vào:
1 100
1
Dữ liệu ra:
1

Giới hạn:

  • 1 ≤ n ≤ 10^5 1 ≤ a_i ≤ 10^5 ;
  • Subtask \#1: a_i đôi một phân biệt.