divisor01

Xem PDF

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

Cho tập hợp số tự nhiên không vượt quá \(n\) (là số chẵn và cho trước)

\(S = \{1, 2, 3, 4\dots\, n-1, n\}\)

Hỏi phải lấy ít nhất bao nhiêu số từ tập hợp \(S\) để có \(2\) số sao cho tổng của chúng chia hết cho \((n + 1)\).

Rõ hơn, tìm \(x\) nhỏ nhất sao cho mọi tập con \(x\) phần tử của \(S\) tồn tại 2 số khác nhau có tổng chia hết cho \((n + 1)\).

Yêu cầu: Nhập \(n(2 \leq n \leq 10^9)\), in ra \(x\).

Example

Test 1

Input
4
Output
3
Note

Các tập con 3 phần tử của \(S\) là:

\({1, 2, 3}\) \(\rightarrow\)\((2 + 3)\) chia hết cho 5

\({1, 2, 4}\) \(\rightarrow\)\((1 + 4)\) chia hết cho 5

\({1, 3, 4}\) \(\rightarrow\)\((1 + 4)\) chia hết cho 5

\({2, 3, 4}\) \(\rightarrow\)\((2 + 3)\) chia hết cho 5


Bình luận