TLE-oj Cup Round 2 - GCD khác một - TLEOJ: TLE Online Judge

TLE-oj Cup Round 2 - GCD khác một

Điểm: 1600 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 128M

Input: GCDONE.inp

Output: GCDONE.out

Tác giả:

Sunlight

Dạng bài

Bạn được cho một dãy số nguyên dương $a_1$ , $a_2$ , $...$ , $a_n$ . Với mỗi thao tác, bạn được phép tăng hoặc giảm một phần tử bất kỳ $1$ đơn vị. Tìm số thao tác ít nhất để làm cho dãy sau khi biến đổi có ước chung lớn nhất lớn hơn $1$ .

Input, Output và Subtasks

Input (GCDONE.inp)

Dòng đầu tiên là một số nguyên dương $n \le 10^5$ - số phần tử của dãy.
Dòng tiếp theo gồm $n$ phần tử $a_1$ , $a_2$ , $...$ , $a_n$ , $1 \le a_i \le 10^7$ .

Output (GCDONE.out)

Một dòng duy nhất gồm kết quả bài toán - số thao tác biến đổi ít nhất để ước chung lớn nhất của dãy thu được lớn hơn $1$ .

Subtasks

Subtask 1 $(5\%)$ : $n \le 10$ .
Subtask 2 $(5\%)$ : $a_i \le 2$ .
Subtask 3 $(10\%)$ : $a_i \le 3$ .
Subtask 4 $(10\%)$ : $a_i \le 1000$ .
Subtask 5 $(15\%)$ : $n, a_i \le 10^4$ .
Subtask 6 $(15\%)$ : $n \le 1000$ .
Subtask 7 $(20\%)$ : $a_i \le 10^5$ .
Subtask 8 $(20\%)$ : Không có giới hạn gì thêm.

Sample

Input (GCDONE.inp)

5
5 11 15 20 23

Output (GCDONE.out)

Notes

Cần $3$ thao tác để biến đổi dãy ban đầu thành $(5, 11 - 1, 15, 20, 23 + 2)$ có ước chung lớn nhất là $5$ .

Bình luận

Không có bình luận nào.