Modulo nhỏ nhất

Điểm: 8,00 (OI)

Giới hạn thời gian: 2.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Cho $n$ số nguyên phân biệt $a_{1}, a_{2}, \dots, a_{n}$ . Bạn được phép xóa nhiều nhất $k$ số trong dãy. Hãy tìm số nguyên dương $m$ nhỏ nhất sao cho với mọi cặp số $a_{i}, a_{j}$ còn lại (sau khi xóa) thì:

$a_{i} ≢ a_{j} (\mod m)$

Nói cách khác, các số còn lại đều có số dư khác nhau khi chia cho $m$ .

Dữ liệu vào

Dòng đầu chứa hai số nguyên $n$ và $k$ .
Dòng thứ hai chứa $n$ số nguyên phân biệt $a_{1}, a_{2}, \dots, a_{n}$ .

Dữ liệu ra

In ra một số nguyên dương duy nhất là $m$ nhỏ nhất thỏa mãn.

Ràng buộc

$1 \leq n \leq 5000$
$0 \leq k \leq 4$
$0 \leq a_{i} \leq 10^{6}$
Các $a_{i}$ đôi một phân biệt.

Ví dụ

Input	Output	Giải thích
7 0 0 2 3 6 7 12 18	13	Không được xóa số nào. Với $m = 13$ , các số dư là $0, 2, 3, 6, 7, 12, 5$ — đôi một khác nhau. Mọi $m < 13$ đều có ít nhất hai số trùng số dư.
7 1 0 2 3 6 7 12 18	7	Cho phép xóa $1$ số. Với $m = 7$ , số dư của $0$ và $7$ đều là $0$ ; xóa một trong hai số đó thì các số còn lại có số dư phân biệt.

Bình luận

Không có bình luận tại thời điểm này.