NOI '10 P1 - Energy Harvesting
View as PDFNational Olympiad in Informatics, China, 2010
DongDong owns a rectangular strip of land. On it, he can plant a special type of energy plant with the ability to harvest energy from the sun. After the plants have harvested the energy, DongDong will use an energy pooling machine to gather all the solar energy collected by the plants to one place.
DongDong's plants are neatly arranged into  rows, with 
plants in each row. The vertical and horizontal distances between
adjacent plants are all the same. Thus, each of DongDong's plants can be
represented with the coordinates 
, where 
 can be from 
 to 
,
and 
 can be from 
 to 
, indicating that the plant is in column 
 of
row 
.
Since the energy pooling machine is rather large and hard to move,
DongDong has placed it into a corner with the coordinates . In the
process of pooling energy, a certain amount of energy is bound to be
lost. If the line segment formed between a plant and the pooling machine
intersects with 
 other plants, then the energy lost will be 
units. For example, the machine is collecting energy from the plant at
, but since one plant at 
 is on the line segment between
them, the energy lost will be 
. Note: if there are no other plants on
the line segment, then 
 unit of energy will be lost. Now, you must
determine the total energy loss of the pooling process.
Following is an example of energy pooling for  and 
. There
are a total of 
 plants. The number labeled beside each plant
represents the energy loss for that plant.
In this example, the total energy lost is .
Input Specification
The input consists of a single line with two integers  and 
.
Output Specification
The output should consist of a single integer, representing the total energy loss.
Sample Input 1
5 4
Sample Output 1
36
Sample Input 2
3 4
Sample Output 2
20
Constraints
For  of test cases: 
.
For  of test cases: 
.
For  of test cases: 
.
For  of test cases: 
.
For  of test cases: 
.
Problem translated to English by .
Comments