51nod 1138 连续整数的和 好题

给出一个正整数N,将N写为若干个连续数字和的形式(长度 >= 2)。例如N = 15,可以写为1 + 2 + 3 + 4 + 5,也可以写为4 + 5 + 6,或7 + 8。如果不能写为若干个连续整数的和,则输出No Solution。

 收起

输入

输入1个数N(3 <= N <= 10^9)。

输出

输出连续整数中的第1个数,如果有多个按照递增序排列,如果不能分解为若干个连续整数的和,则输出No Solution。

输入样例

15

输出样例

1
4
7

分析:

假设[a,a+k-1]满足和=n

a,a+1, a+2,……a+k-1

k*a+k*(k-1)/2=n

k^2+(2*a-1)k-2n=0

这题一开始想的暴力枚举a,

k=【(1-2a)+(long long)(2*a-1)*(long long)(2*a-1)+8*n】/2

果断的T了

这题需要转化一下啊思想

枚举k

k^2+k=2n

取a=1,k可以取到最大不超过sqrt(2*n)

即k的取值范围(2,sqrt(2*n))

 

超时代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int main()
{
	int n;
	while(~scanf("%d",&n))
	{
		int flag=1;
	    for(int a=1;a<=n/2;a++)
		{
		  double x=(long long)(2*a-1)*(long long)(2*a-1)+8*n;
		  x=sqrt(x);
		  if(x==(int)x)
		  {
		  	if(((int)x+1-2*a)%2==0)
			{
				printf("%d\n",a);
				flag=0;
			}
		  }
		}
		if(flag==1)
			printf("No Solution\n");
	}
	return 0;
}

AC代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int main()
{
	int n;
	scanf("%d",&n);
	
		int flag=1;
	    for(int k=sqrt(2*n);k>=2;k--)
		{
		   if((2*n+k-k*k)%(2*k)==0)
		   {
			printf("%d\n",(2*n+k-k*k)/(2*k));
			flag=0;
		   }
             
		}
		if(flag==1)
			printf("No Solution\n");

	return 0;
}

 

上一篇:PAT 甲级 1138 Postorder Traversal (25 分) 先序中序->后序


下一篇:【原创】运维基础之Docker(3)搭建私有仓库