Problem Statement
Once upon a time, there lived a migrant barbarian tribe. Every time it settled down, a tent was set for the chief of the tribe. First, an area was selected and divided into NxM squares with side lengths of 1 unit. Then, they chose a site for the tent in such a way that every vertex of its base coincided with some vertex of one of the squares. According to an ancient tradition, the base had to be a rhomb. For example, there are all 6 different possible sites for the tent in a 2x2 area:
An example of a tent in a 4x2 area:
For a given N and M, return the number of different possible sites for the chief's tent. Two sites are different if there is at least one vertex which belongs to one site but not the other.
Definition
- Class:
- SettingTents
- Method:
- countSites
- Parameters:
- int, int
- Returns:
- int
- Method signature:
- int countSites(int N, int M)
- (be sure your method is public)
Notes
- A rhomb is a four-sided polygon with sides of equal length.
- The tent must have non-zero area.
Constraints
- N will be between 1 and 100, inclusive.
- M will be between 1 and 100, inclusive.
Examples
2
2
Returns: 6
The example from the problem statement.
1
6
Returns: 6
The only possible sites are the squares of the area themselves.
6
8
Returns: 527
100
100
Returns: 38235298
98
99
Returns: 35869694
1
1
Returns: 1
26
1
Returns: 26
100
1
Returns: 100
1
100
Returns: 100
1
56
Returns: 56
2
27
Returns: 262
66
2
Returns: 1286
3
3
Returns: 22
9
3
Returns: 120
3
88
Returns: 4900
4
100
Returns: 12716
25
25
Returns: 111977
44
46
Returns: 1324538
50
50
Returns: 2068014
31
74
Returns: 1362536
31
75
Returns: 1393342
31
76
Returns: 1424388
31
77
Returns: 1455562
77
78
Returns: 13083584
77
79
Returns: 13433601
77
80
Returns: 13790536
81
84
Returns: 17003180
91
90
Returns: 25121322
91
91
Returns: 25714110
91
92
Returns: 26312048
91
93
Returns: 26912486
100
90
Returns: 30481429
66
33
Returns: 1316270
11
97
Returns: 138062
37
81
Returns: 2489211
99
100
Returns: 37429856
100
99
Returns: 37429856
61
17
Returns: 209747
32
64
Returns: 1155462
64
88
Returns: 10973510
81
27
Returns: 1107492
20
20
Returns: 43850
21
29
Returns: 101297
48
98
Returns: 6621616
45
35
Returns: 760000
40
31
Returns: 458936
83
28
Returns: 1267800
45
69
Returns: 3043939
26
64
Returns: 683457
52
70
Returns: 4399078
49
44
Returns: 1505592
73
26
Returns: 848910
59
89
Returns: 9247310
2
7
Returns: 32
20
71
Returns: 409116
31
70
Returns: 1241480
91
26
Returns: 1210502
71
78
Returns: 10985040
3
18
Returns: 350
68
30
Returns: 1089123
56
17
Returns: 183052
5
65
Returns: 9891
65
74
Returns: 8137442
100
21
Returns: 798880
71
79
Returns: 11268888
18
44
Returns: 143459
52
68
Returns: 4163986
32
33
Returns: 336720
19
15
Returns: 20940
38
16
Returns: 83288
86
75
Returns: 15076350
22
2
Returns: 186
82
79
Returns: 15331400
99
89
Returns: 29142341
97
99
Returns: 35099673
100
98
Returns: 36634311
99
99
Returns: 36645046
98
67
Returns: 14932418