问题1021--求和

1021: 求和

时间限制: 1 Sec  内存限制: 128 MB
提交: 30  解决: 27
[提交] [状态] [讨论版] [命题人:]

题目描述

给定一个n,让大家求前n项的和这个问题很简单。现在罗老师要改变一下规则,对于前n项的数字,罗老师可以改变其正负,比如前4项,本来是1+2+3+4=10 罗老师可以改变这些数字的正负,比如把13变为负数,那么前四项和就变为-1+2-3+4=2

现在罗老师想知道,在这种规则下,能不能取前n项,使得和为s

如果可以,输出最小的n,不可以输出-1

输入

输入s

输出

输出n

样例输入 Copy

12

样例输出 Copy

7

提示

【样例说明】

要使得和为12,罗老师可以取前7项,将17变负

12=-1+2+3+4+5+6-7

【数据规模和约定】

0<s<=100000


题解:

A=1+2+..n

如果要改变某些值为负数,使得和为A,相当于B=A-2*ai

说明A-B=2*ai, 即两个sum的差一定为偶数

所以只要枚举n,使得前n项的和,减去S为偶数,那么肯定有解

2*ai相当于前n项里找到一些项,使得和为ai,这个是一定可以的

连续的n项去取一些数可以组成任意正整数

其实只要1248。。。这些数,就可以组成任意正整数,因为二进制的每一位都包括了

来源/分类

数学