NOI '10 P1 - Energy Harvesting

View as PDF

Points: 17 (partial)
Time limit: 0.6s
Memory limit: 512M

Problem type
National Olympiad in Informatics, China, 2010

DongDong owns a rectangular strip of land. On it, he can plant a special type of energy plant with 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 Alex.