HDU 2058 The sum problem 数学题

时间:2024-09-01 13:05:14

解题报告:可以说是一个纯数学题,要用到二元一次和二元二次解方程,我们假设[a,b]这个区间的所有的数的和是N,由此,我们可以得到以下公式:

(b-a+1)*(a+b) / 2 = N;很显然,这是一个二元一次方程,如果可以解出这个方程里的a,b就可以了,N是已知的,那么可以怎么一个公式怎么解二元方程呢?这里有两种方法可以选择,第一种是可以枚举a = 1,2,3.....,一直枚举到N/2,a是不可能大于N/2,这个你可以自己证明一下,但是这样做的缺点就是数据量还是太大了,N/2任然达到了10的八次方级别,所以这种方法不行(我一开始就是用这种枚举的),然后就是第二种,很明显,我们可以看到,a到b的区间的长度一定是唯一的,就是说如果区间的长度固定,a和b 的值也就固定了,经过证明之后,发现,这种枚举的方法,只需要从0枚举到sqrt(2*N),很显然,这样将运算量从10的九次方一下子降到了10的4.5次方,数据就可以过了。我们可以设区间的长度为l,首先有:l = b-a;再加上(b-a+1)*(a+b) / 2 = N这个公式,我们可以分别求出a和b,但是 这个a和b求出来不一定是满足要求的,很简单,因为我们枚举的从1到sqrt(2*N),中间有些长度的区间可能就没有,不过,还好,我们可以通过判断算出来的a和b的结果是否是整数并且大于0来判断这一对a和b的解是否是可行解。

 #include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
double N,M;
int judge(double x) {
if(x <= )
return ;
return x - (int)x == ;
}
int main() {
while(scanf("%lf%lf",&N,&M),N,M) {
double n = min(N,M);
for(double i = (int)sqrt(2.0*n)+;i >= ;--i) {
double a = (2.0 * n - i*i - i) / (*i+);
double b = ( * n + i*i + i) / (2.0 * i + 2.0);
if(judge(a) && judge(b))
printf("[%.0lf,%.0lf]\n",a,b);
}
printf("\n");
}
return ;
}