HDU 2058 The sum problem 数学题

解题报告:可以说是一个纯数学题,要用到二元一次和二元二次解方程,我们假设[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的解是否是可行解。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 using namespace std;
 5 double N,M;
 6 int judge(double x) {
 7     if(x <= 0)
 8     return 0;
 9     return x - (int)x == 0;
10 }
11 int main() {
12     while(scanf("%lf%lf",&N,&M),N,M) {
13         double n = min(N,M);
14         for(double i = (int)sqrt(2.0*n)+1;i >= 0 ;--i) {
15             double a = (2.0 * n - i*i - i) / (2*i+2);
16             double b = (2 * n + i*i + i) / (2.0 * i + 2.0);
17             if(judge(a) && judge(b))
18             printf("[%.0lf,%.0lf]
",a,b);
19         }
20         printf("
");
21     }
22     return 0;
23 }
View Code
原文地址:https://www.cnblogs.com/xiaxiaosheng/p/3265145.html