问题描述
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]
问题分析
Problem Analyse
给出一个数列1，2，3，......N，你所要做的就是算出和为M的所有连续的数列。
简单数学题。
Algorithm Analyse
我们都知道，在连续的整数序列里，1, 2, 3, ..., n-1, n, n+1, ...
∵ 2n = [(n-1) + (n+1)] = [(n-2) + (n+2)] = ... = [1 + (2n-1)]
∴ (n-m) + (n-m+1) + ... + n-1 + n + n+1 + ... + (n+m-1) + (n+m) = (2m+1) × n
∵ 2m+1是奇数
∴ 如果X能被2m+1整除(即能被分割成2m+1份)，且n = X / (2m+1)
则X = (n-m) + (n-m+1) + ... + n-1 + n + n+1 + ... + (n+m-1) + (n+m)
同理，在整数序列中，又有这样的规律:
∵ n + (n+1) = (n-1) + (n+2) = ... = 1 + 2n
∴ (n-m) + (n-m+1) + ... + (n+m+1) = (m+1)(2n+1)
∴ 如果X能被(2n+1)整除，且X / (2m+2) = n
则X = (n-m) + (n-m+1) + ... + (n+m+1)
运算的时候，保证n-m大于0，n+m+1或n+m小于给定的上界即可。