首页 > 代码库 > HDU-2058-The sum problem(数学题技巧型)

HDU-2058-The sum problem(数学题技巧型)

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=2058

思路:

这题的n,m都很大,很显然直接暴力,会超时,那就不能全部都找了,利用等差数列求和公式,

(1)sn=n*(a1+an)/2; 即可代入公式,(2)m=(e-s+1)*(s+e)/2                         注释*******//s代表起点,e代表终点。

则由(2)推出,(3)e=(int)(2*m+s*s-s),根据e点找s点,代入(1)成立则输出[s,e]; 但新的

问题又出现了由于m可能很大所以(3)中e可能太大而溢出。也不行,

同样的思路,可以换一种写法,(4)m=j*(i+i+j-1)/2                                                                 注释*****//i代表起点,j代表数的个数;

那么 j=sqrt(2*m);  j>=1;j-- 一直递减找下去,由j算出i,代入i,j 如果 (4)成立

则输出【i,i+j-1】;

 

我的AC代码

#include<stdio.h>
#include<math.h>
int main(void)
{
int n,m,i,j;
while(scanf("%d%d",&n,&m)==2&&(n+m))
{
for(j=sqrt(2*m);j>0;j--)
{
i=(2*m/j-j+1)/2;
 if(i+j-1<=n)                                      //这个题,数据很不全,这一行如果不写同样可过,但是错的, 如 n< m 错误就体现出来了。
if(j*(2*i+j-1)==2*m)
{
printf("[%d,%d]\n",i,i+j-1);
}
}
printf("\n");
}
return 0;
}

HDU-2058-The sum problem(数学题技巧型)