Bội chính phương (Tin học trẻ B - Vòng Toàn quốc 2020)

Xem PDF

Điểm: 1500 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Cho một dãy số \(A\)\(N\) phần tử. Tìm số nguyên dương \(P\) nhỏ nhất thỏa mãn: \(P\) là số chính phương và \(P\) chia hết cho tất cả các phần tử của dãy số \(A\).

Yêu cầu: In ra phần dư của phép chia khi chia \(P\) cho \(10^9+7\).

Input

  • Dòng đầu tiên chứa số nguyên dương \(N\) là số lượng phần tử của dãy số.
  • Dòng tiếp theo chứa \(N\) số nguyên dương \(a_i\) là các phần tử của dãy số \(A\) (\(1 \le i \le N\)).

Output

  • Một số nguyên duy nhất là kết quả của bài toán.

Scoring

  • Subtask \(1\) (\(30\%\) số điểm): \(N \le 10, a_i \le 10\).
  • Subtask \(2\) (\(30\%\) số điểm): \(N \le 10^4, a_i \le 10^5\).
  • Subtask \(3\) (\(40\%\) số điểm): \(N \le 10^5, a_i \le 10^7\).

Example

Test 1
Input
3
2 1 3
Output
36

Bình luận


  • 0
    penistone    7:43 a.m. 19 Tháng 8, 2024

    bài này lại phải phân tích thừa số nguyên tố bình thường chứ sàng ước là TLE ;-;

    • 2 bình luận nữa