| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P142PROJ - ROUND 2J - Hệ thống mê cung |
Tèo nằm mơ thấy mình trở thành giám đốc của Công viên Thủ lệ. Để cho công viên thêm phần thú vị, Tèo quyết định đầu tư xây dựng một mê cung dài loằng trong công viên, nó gồm hệ thống các phòng tham quan trên mặt đất, và hệ thống đường đi ngầm dưới lòng đất. Tổng công trình sư cho hệ thống này, không ai khác, chính là người bạn thân của Tèo, kĩ sư Tí.
Có n phòng tham quan nổi trên mặt đất, mỗi phòng mang một số hiệu riêng a_i. Lối vào bắt đầu ở phòng có số hiệu nhỏ nhất, và lối ra ở phòng có số hiệu lớn nhất. Kĩ sư Tí quyết định thiết kế như sau: sẽ đào đường hầm tham quan 2 chiều giữa 2 phòng mang số hiệu x và y, nếu chúng có ước chung lớn hơn 1. Lưu lượng người tối đa có thể di chuyển trong đường hầm này bằng UCLN(x,y) người/1 phút (lưu lượng tối đa chiều đi = lưu lượng tối đa chiều về = UCLN(x,y)). Khách tham quan một khi bị lạc vào mê cung rồi, sẽ đi liên tục trong hệ thống mê cung này.
Sau khi xem qua bản thiết kế của Tí, Tèo đã yêu cầu Tí tính toán xem số lượng người tối đa có thể tham quan mê cung sao cho hệ thống đường hầm giao thông này không bị tắc nghẽn?
Input
Dòng đầu tiên là số nguyên dương n (2 <= n <= 1000) là số phòng của hệ thống mê cung.
n dòng tiếp theo, mỗi dòng gồm một số nguyên là số hiệu của phòng thứ i. Giá trị này nằm trong đoạn [2, 2*10^9].
Output
In ra lưu lượng người lớn nhất có thể vào mê cung/phút. (Lưu lượng tối đa là 10^9 người/phút).
Example
Test 1:
Input:
4
4
6
8
9
Output:
3
Test 2:
Input:
7
25289
17017
2601
325
225
55223
190969
Output:
18
| Được gửi lên bởi: | adm |
| Ngày: | 2014-02-08 |
| Thời gian chạy: | 5s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
