acm2058[通俗易懂]

int main(){     
int n,m; 
int l,i,a,b,s; 
while (scanf(“%d%d”,&n,&m),n + m)    
{ 
l = (int)sqrt(2 * m); 
for (i = l; i >= 1; i–)        
{ 
s = (2*m + i – i*i)/2; 
if(s % i == 0)           
{ 
a = s / i; 
if(a+i-1 > n) break; 
printf(“[%d,%d]\n”,a,a + i – 1); 
} 
} 
printf(“\n”);   
} 
return 0; 
}  

最后，说一下我对代码的解释

假设:1,2,3,…,n中的i个数(a1,a2,…,ai)满足sum(a1,a2,…,ai)=m。

那么，1<=a1<=m，

当a1=1时，i=ai，i取得最大值，由于i*(1+i)/2=m，i=sqrt(2*m-i)<sqrt(2*m)；

当a1=m时，i=1，i取得最小值。

所以，1<=i<=sqrt(2*m)。

同时我们知道，两个长度都为i却不相同的连续数列，它们的和不可能都等于m。

从上面的讨论可知，满足要求的数列的长度i在[1,sqrt(2*m)]之间，且不重复。

现在从sum(a1,a2,…,ai)=m反推，由于ai=a1+i-1,可知：

sum(a1,a2,…,ai) = (a1+ai)*i/2 = (a1+a1+i-1)*i/2= m

a1*i = (2*m+i-i*i)/2 = s

那么，存在1,2,3,…,n中的i个数(a1,a2,…,ai)满足sum(a1,a2,…,ai)=m，

等价于，对于s=(2*m+i-i*i)/2有：s%i=0(因为a1=s/i),且s/i+i-1<=n(因为ai=s/i+i-1)