Solution to Continue Sequence With Sum from Jobdu

9 Sep

Question (in Chinese): http://ac.jobdu.com/problem.php?pid=1354

Question Name: Continue Sequence With Sum

Question Description: given a target integer, show all the positive integer arithmetic sequence, whose sum is equal to the target.

Input: the input might contain multiple test cases. Each line is an integer S (S <= 1,000,000). When S is negative, quit the program.

Output: if the sequence(s) exist, print them out, and the sequence with the smallest first-number shows firstly. If it does not exist, print out a line “Pity!”. After each test case, print a line with “#”.

The official solution in the book is slow. We can have a better solution. With the given target T, we want an integer sequence, whose sum is T. The sequence could be represented as a1, a2, a3, …, an, such that:

a1 + a2 + a3 + … + an = T

Because it is a arithmetic sequence, we could simplify it as:

(a1 + an) * n / 2 = T

(a1 + (a1 + n – 1)) * n / 2 = T

(2 * a1 + n -1) * n = 2 * T    (1)

where n is the size of the sequence.

Because a1 >= 1 (positive sequence), from equation 1, we have:

n^2 = 2 * T – (2 * a1 – 1) * n < 2 * T

n < sqrt(2 * T)               (2)

Currently, we can reduce the range of the sequence size to [2, sqrt(2 * T)]. Then we will consider the start point of the sequence. Also from the equation 1, we could get:

a1 = (2*T/n – n + 1) / 2

Please notice all symbols in the equation is the positive INTEGERS. So to get a legal start point a1, we have have two condition:

2 * T % n == 0 AND (2*T/n – n + 1) % 2 == 0                  (3)

With equation 2 and 3, for the given target T, we could find the start integer and size of all the qualified sequences. And that is our solution.

Leave a Reply

Your email address will not be published. Required fields are marked *