divisor01


Submit solution

Points: 200 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem types

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\).

Input

4

Output

3

GIẢI THÍCH:

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

\({1, 2, 3}\) -> có \((2 + 3)\) chia hết cho 5

\({1, 2, 4}\) -> có \((1 + 4)\) chia hết cho 5

\({1, 3, 4}\) -> có \((1 + 4)\) chia hết cho 5

\({2, 3, 4}\) -> có \((2 + 3)\) chia hết cho 5


Comments

There are no comments at the moment.