题目
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;
}