Problem Statement
Note that the memory limit for all tasks in this SRM is 256 MB.
You are given
These lines divide the plane into several regions. (Some of them are finite, some are infinite.) Compute and return the total number of regions.
Definition
- Class:
- LotsOfLines
- Method:
- countDivisions
- Parameters:
- int, int
- Returns:
- long
- Method signature:
- long countDivisions(int A, int B)
- (be sure your method is public)
Notes
- Formally, the line with the equation y=ax+b is the set of all points (x,y) such that x is any real number and y=ax+b.
Constraints
- A will be between 1 and 1,200, inclusive.
- B will be between 1 and 1,200, inclusive.
Examples
1
1
Returns: 2
There is only one line: y=0. This line divides the plane into two regions.
2
2
Returns: 9
There are four lines. The plane looks as follows.
3
2
Returns: 17
1
1200
Returns: 1201
There are 1,200 horizontal lines.
5
9
Returns: 638
500
500
Returns: 18997978639
1200
1200
Returns: 630301012623
1199
1200
Returns: 629250802361
1200
1199
Returns: 629250802362
1200
1
Returns: 2400
1
1200
Returns: 1201
1
1
Returns: 2
2
1
Returns: 4
3
1
Returns: 6
1
2
Returns: 3
2
2
Returns: 9
3
2
Returns: 17
1
3
Returns: 4
2
3
Returns: 16
3
3
Returns: 32
150
138
Returns: 130256183
88
37
Returns: 3223300
96
29
Returns: 2354936
74
200
Returns: 66583275
5
45
Returns: 15074
1191
1169
Returns: 589217910486
1139
1179
Returns: 548149275716
1162
1155
Returns: 547520250746
1165
1112
Returns: 510134349553
1139
1140
Returns: 512484902549
1112
1178
Returns: 521583006399
1193
1143
Returns: 565192984788
1194
1132
Returns: 555296584641
1194
1149
Returns: 572100259808
1181
1101
Returns: 513921912602
44
1135
Returns: 757813108
97
1107
Returns: 3504413828
84
1132
Returns: 2748398323
90
1105
Returns: 3006485588
43
1174
Returns: 774064727
1151
29
Returns: 338156898
1158
10
Returns: 40560915
1152
40
Returns: 645197883
1111
60
Returns: 1350423181
1102
48
Returns: 850309279
1122
1122
Returns: 481719582617