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 “#”.
1 2 3 4 5 6 7 8 9 10 11 12 13 | Input: 4 5 100 -1 Output: Pity! # 2 3 # 9 10 11 12 13 14 15 16 18 19 20 21 22 # |
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 an 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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 | /*---------------------------------------------------------------- * Author: Sheng Yu - codesays.com * Written: 09/09/2014 * Last updated: 09/09/2014 * * Filename: ContinueSequenceWithSum.java * Compilation: javac ContinueSequenceWithSum.java * Execution: java ContinueSequenceWithSum * JDK Used: 1.7 *----------------------------------------------------------------*/ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; /** * The utility to find the consecutive sequence, whose sum is the given value. * @author Sheng Yu codesays.com */ public class ContinueSequenceWithSum { /** * Find all the consecutive sequence, whose sum is the given target. * @param target the target value for the sum. */ public static void findConsecutiveSequence(int target) { StringBuilder sb = new StringBuilder(); boolean found = false; int first = 0; for (int count = (int) Math.sqrt(target << 1); count > 1; --count) { if ((2 * target) % count == 0) { first = (2 * target) / count - count + 1; if ((first & 1) == 0) { // Find one sequence. found = true; first /= 2; sb.append(first); for (int i = 1; i < count; ++i) { sb.append(" "); sb.append(first + i); } sb.append("n"); } } } if (!found) sb.append("Pity!n"); sb.append("#n"); System.out.print(sb); return; } /** * Stub for test. * @param args the command line arguments. * @throws IOException when input gets error. */ public static void main(String[] args) throws IOException { StreamTokenizer st = new StreamTokenizer(new BufferedReader( new InputStreamReader(System.in))); int target = 0; while (st.nextToken() != StreamTokenizer.TT_EOF) { target = (int) st.nval; if (target < 0) break; else findConsecutiveSequence(target); } return; } } |