Energy Harvesting
Time limit1sMemory limit512 MB
Sum over all lattice points (x,y) with 1<=x<=n, 1<=y<=m of 2*gcd(x,y)-1, the energy lost reaching that point from the origin.
- Level
Medium7 of 10
- Topics
- Number theory, Math, Prefix sum, Combinatorics
- Solved
- No attempts yet
Problem
DongDong owns a rectangular strip of land. On it, he can plant a special type of energy plant that harvests energy from the sun. After the plants have harvested the energy, DongDong uses an energy pooling machine to gather all the solar energy collected by the plants into one place.
DongDong's plants are arranged neatly into n rows, with m 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 by the coordinates (x, y), where x ranges from 1 to n and y ranges from 1 to m, indicating that the plant is in column y of row x.
The energy pooling machine is rather large and hard to move, so DongDong has placed it in a corner at the coordinates (0, 0). 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 k other plants, then the energy lost is 2k + 1 units. For example, the machine is collecting energy from the plant at (2, 4), but since one plant at (2, 1) lies on the line segment between them, the energy lost is 3. Note: if there are no other plants on the line segment, then 1 unit of energy is lost. Now you must determine the total energy loss of the pooling process.
The following is an example of energy pooling for n = 5 and m = 4. There are 20 plants in total. The number labeled beside each plant represents the energy loss for that plant.
In this example, the total energy lost is 36.
Input
The input consists of a single line with two integers n and m.
Output
The output consists of a single integer, the total energy loss.
Constraints
1 ≤ n, m ≤ 100,000