SummingArithmeticProgressions
SRM 385 · 2007-12-27 · by Petr
Problem Statement
A magic arithmetic progression with k elements is a sequence of the form x, x+d, x+2*d, ..., x+(k-1)*d for some positive integers x and d. How many integers between left and right, inclusive, can be represented as the sum of some magic arithmetic progression with exactly k elements?
Constraints
- left will be between 1 and 1000000000, inclusive.
- right will be between left and 1000000000, inclusive.
- k will be between 2 and 5, inclusive.
1 12 3 Returns: 3
The representable numbers are: 6=1+2+3, 9=2+3+4=1+3+5, 12=3+4+5=2+4+6=1+4+7. Note that there can be several possible representations for a number.
1 10 2 Returns: 8
Every number except 1 and 2 is representable: 3=1+2, 4=1+3, 5=1+4, etc.
20 30 4 Returns: 6
The representable numbers are 20, 22, 24, 26, 28 and 30.
1 9 4 Returns: 0
The minimal possible sum is 1+2+3+4=10.
1 13 4 Returns: 1
And the next possible sum is 2+3+4+5=14.
Submissions are judged against all 144 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SummingArithmeticProgressions with a public method int howMany(int left, int right, int k) · 144 test cases · 2 s / 256 MB per case