题目

The sum problem

题解

参考博客：
The sum problem(hdu 2058)解题报告

高斯公式： 1+2+…+n=n*(n+1)/2
sum(a,b)定义为从a到b的总和。
目标：求a, b。
sum(a,b)=sum(1,b) –sum(1,a-1)
令c=a-1，
代入 sum(a,b)=M，
得到 (b-c)(b+c+1)=m*2。
假设m * 2有2个因子，分别为x和y(y>x)，
有： y = b+c+1 x = b - c。
解方程得： b=(y+x-1)/2 c=(y-x-1)/2 ,a=(y-x+1)/2

接下来对x, y进行匹配，只要是因数对就看看是否满足条件——x, y使得a, b为整数。

代码

#include<bits/stdc++.h>
using namespace std;
int main() {int n, m, a;while(scanf("%d%d", &n, &m), m && n) {//根据推导先乘2 m *= 2;//i遍历去找2*m的因数 for(int i = (int)sqrt((double)m); i >= 2; i --) {if(m % i == 0) {a = m / i + 1 - i;if (a >= 2 && a % 2 == 0) {a /= 2;if(a + i - 1 <= n)printf("[%d,%d]\n", a, a + i - 1); }}}m /= 2;//从1到n找，如果m比n小，那么就会有1*m这对因子被忽略 if(n >= m) printf("[%d,%d]\n", m, m);printf("\n");}return 0;
}