HDOJ2058题

[cce]
Problem Description
Given a sequence 1,2,3,......N, your job is to calculate all the possible sub-sequences that the sum of the sub-sequence is M.
 

Input
Input contains multiple test cases. each case contains two integers N, M( 1 <= N, M <= 1000000000).input ends with N = M = 0.
 

Output
For each test case, print all the possible sub-sequence that its sum is M.The format is show in the sample below.print a blank line after each test case.
 

Sample Input
20 10
50 30
0 0
 

Sample Output
[1,4]
[10,10]

[4,8]
[6,9]
[9,11]
[30,30]
[/cce]

自己通过列举得出了关系。

[cce_cpp]
#include <stdio.h>

int main(){
	long long int N, M;
	long long int i;
	while (~scanf("%lld%lld", &N, &M))
	{
		if (M == 0 && N == 0)break;
	/*	if (M / 2 > N) i = N;
		else i = M / 2;*/
		long long temp=0;
		for (i = 1;temp<=M; i++)//若前i项和就比M大，那么不可能有i项
		{
			temp = i*(i + 1) / 2;
		}
		i--;

		for (i; i >0; i--)//i为数列的项数，项数为偶数则数列的平均值为小数，项数为奇数则数列的平均值为整数
		{
			if (M%i == 0 && i % 2 == 1 && (M / i - (i / 2))>0)//M是i的整数倍或者.5倍
				printf("[%lld,%lld]\n", M / i-(i/2), M / i+i/2);
			else if (M%i != 0&&(M * 2) % i == 0 && i % 2 == 0 && (M / i - ((i - 1) / 2))>0)
				printf("[%lld,%lld]\n", M / i - ((i - 1) / 2), M / i + (i - 1) / 2+1);
		}
		printf("\n");

	}
	return 0;
}
[/cce_cpp]

网上查到的算法，需要的数学归纳更多。

[cce_cpp]
#include <stdio.h>
#include <math.h>
int main(){
	long long int M,N;
	long long int d,j;
	while (~scanf("%lld%lld", &N, &M))
	{
		if (M == 0 && N == 0)break;
		for(d =sqrt(2*M);d>0;d--){//d是整个区间长度
			j = M-(d+d*d)/2;
			if(j%d==0)
				printf("[%lld,%lld]\n", j/d+1,j/d+d);
		}
		printf("\n");
	}
}
/*
a+1 a+2 ……a+d
和M = a*d+(1+d)*d/2 = (a+(1+d)/2)*d
必有d*d/2<M
a*d = M-(1+d)*d/2 = j
若满足条件，必有j是d的倍数
a+1 = j/d+1
a+d = j/d+d

*/
[/cce_cpp]