A8074. Interesting Game
编程题
普及/提高-
知识点
题目描述
Two best friends Serozha and Gena play a game.
Initially there is one pile consisting of $n$ stones on the table. During one move one pile should be taken and divided into an arbitrary number of piles consisting of $a_{1}>a_{2}>...>a_{k}>0$ stones. The piles should meet the condition $a_{1}-a_{2}=a_{2}-a_{3}=...=a_{k-1}-a_{k}=1$ . Naturally, the number of piles $k$ should be no less than two.
The friends play in turns. The player who cannot make a move loses. Serozha makes the first move. Who will win if both players play in the optimal way?
Initially there is one pile consisting of $n$ stones on the table. During one move one pile should be taken and divided into an arbitrary number of piles consisting of $a_{1}>a_{2}>...>a_{k}>0$ stones. The piles should meet the condition $a_{1}-a_{2}=a_{2}-a_{3}=...=a_{k-1}-a_{k}=1$ . Naturally, the number of piles $k$ should be no less than two.
The friends play in turns. The player who cannot make a move loses. Serozha makes the first move. Who will win if both players play in the optimal way?
输入格式
The single line contains a single integer $n$ ( $1<=n<=10^{5}$ ).
输出格式
If Serozha wins, print $k$ , which represents the minimal number of piles into which he can split the initial one during the first move in order to win the game.
If Gena wins, print "-1" (without the quotes).
If Gena wins, print "-1" (without the quotes).
输入输出样例
输入 #1
3
输出 #1
2
输入 #2
6
输出 #2
-1
输入 #3
100
输出 #3
8