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?
Definition
- Class:
- SummingArithmeticProgressions
- Method:
- howMany
- Parameters:
- int, int, int
- Returns:
- int
- Method signature:
- int howMany(int left, int right, int k)
- (be sure your method is public)
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.
Examples
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.
1
1
2
Returns: 0
1
2
2
Returns: 0
1
3
2
Returns: 1
1
4
2
Returns: 2
1
5
2
Returns: 3
1
6
2
Returns: 4
1
1
3
Returns: 0
1
2
3
Returns: 0
1
3
3
Returns: 0
1
4
3
Returns: 0
1
5
3
Returns: 0
1
6
3
Returns: 1
1
7
3
Returns: 1
1
8
3
Returns: 1
1
9
3
Returns: 2
1
10
3
Returns: 2
1
11
3
Returns: 2
1
12
3
Returns: 3
1
10
4
Returns: 1
1
11
4
Returns: 1
1
12
4
Returns: 1
1
13
4
Returns: 1
1
14
4
Returns: 2
1
15
4
Returns: 2
1
16
4
Returns: 3
1
17
4
Returns: 3
1
18
4
Returns: 4
1
19
4
Returns: 4
1
10
5
Returns: 0
1
11
5
Returns: 0
1
12
5
Returns: 0
1
13
5
Returns: 0
1
14
5
Returns: 0
1
15
5
Returns: 1
1
16
5
Returns: 1
1
17
5
Returns: 1
1
18
5
Returns: 1
1
19
5
Returns: 1
1
20
5
Returns: 2
1
21
5
Returns: 2
1
22
5
Returns: 2
1
23
5
Returns: 2
1
24
5
Returns: 2
1
25
5
Returns: 3
1
26
5
Returns: 3
1
27
5
Returns: 3
1
28
5
Returns: 3
1
29
5
Returns: 3
1
1000000000
2
Returns: 999999998
1
1000000000
3
Returns: 333333332
1
1000000000
4
Returns: 499999995
14
14
5
Returns: 0
15
15
5
Returns: 1
16
16
5
Returns: 0
14
14
4
Returns: 1
15
15
4
Returns: 0
16
16
4
Returns: 1
270050871
477356599
3
Returns: 69101910
20
382167388
5
Returns: 76433474
22
859601633
4
Returns: 429800806
1
626486333
3
Returns: 208828776
6
10
4
Returns: 1
18
19
2
Returns: 2
20
26
3
Returns: 2
9
21
2
Returns: 13
83775320
103270600
5
Returns: 3899057
242548845
246930528
2
Returns: 4381684
19
23
2
Returns: 5
41014432
72180459
5
Returns: 6233205
58155282
180514283
5
Returns: 24471800
4
6
4
Returns: 0
633034921
805153700
3
Returns: 57372926
1
2
4
Returns: 0
27
833985333
4
Returns: 416992653
358476492
634066638
4
Returns: 137795074
5
701880154
3
Returns: 233960050
10
250276212
4
Returns: 125138101
546195286
656246848
2
Returns: 110051563
4
16
2
Returns: 13
9
676116746
4
Returns: 338058368
6
478091737
2
Returns: 478091732
2
4
5
Returns: 0
1
3
3
Returns: 0
6
13
3
Returns: 3
163039951
457484471
5
Returns: 58888904
11
21
3
Returns: 4
225235485
313423339
5
Returns: 17637571
16
184459498
4
Returns: 92229742
3
25
4
Returns: 7
4
21
2
Returns: 18
23
861067741
4
Returns: 430533859
8
10
4
Returns: 1
5
582354858
5
Returns: 116470969
10
11
2
Returns: 2
2
844190775
3
Returns: 281396924
7
12
5
Returns: 0
28
32719632
4
Returns: 16359803
15
15
5
Returns: 1
4
403257863
3
Returns: 134419286
280275835
608899014
5
Returns: 65724636
299704889
595092880
5
Returns: 59077599
19
63141083
5
Returns: 12628213
456585908
817933056
2
Returns: 361347149
2
7
4
Returns: 0
9117938
214465231
4
Returns: 102673647
371052252
528386374
5
Returns: 31466824
15
302385366
5
Returns: 60477071
1
100000
4
Returns: 49995
1
999999999
4
Returns: 499999994
1
999999999
5
Returns: 199999997
1
1000000000
5
Returns: 199999998
10
232323290
4
Returns: 116161640
20
1000000000
4
Returns: 499999991
11
1000000000
4
Returns: 499999994
1
10000
4
Returns: 4995
98765
100000000
4
Returns: 49950618
23
1000000000
3
Returns: 333333326
1000000000
1000000000
5
Returns: 1
10000320
23121412
5
Returns: 2624219
1
100000000
4
Returns: 49999995
7
9
3
Returns: 1
12
12
4
Returns: 0
1
654
4
Returns: 322
1
1
4
Returns: 0
100
1000000000
4
Returns: 499999951
11
13
4
Returns: 0
52
52
3
Returns: 0
1
10000
5
Returns: 1998
5
5
5
Returns: 0
10
10
4
Returns: 1
1
100
4
Returns: 45
15
17
4
Returns: 1
17
19
4
Returns: 1
1
30
5
Returns: 4
10
20
5
Returns: 2
3
5
2
Returns: 3
124
123312541
5
Returns: 24662484
16
17
3
Returns: 0
6
6
5
Returns: 0