ZOJ Problem Set - 3473
Radio is a magical thing, isn't it?
There are many (technically, it's infinite) radio stations staying in the universe, and in our case, they are arranged in a matrix. The matrix starts from our planet - the earth, that means we can give coordinates to each radio station in the matrix grid, and the one on the earth has the coordinates (1, 1, 1). So we can identify each radio station by its coordinates (x, y, z). Here x, y and z are all positive integers.
Every radio station has two states, receiving state and sending state. At the beginning, all stations except the one at (1, 1, 1) stay in receiving state, while the one at (1, 1, 1) initially stays in sending state.
While in sending state, station at (x, y, z) will continuously send message which has a message value Sx, y, z to all the other stations, and the message been sent out is encoded by this station's coordinates (x, y, z), that means only the stations which have coordinates (x', y', z') (here x' is multiple of x, y' is multiple of y, z' is multiple of z, but (x', y', z') cannot be the same to (x, y, z) ) can decode the message sent by station (x, y, z). Here S1, 1, 1 = 1.
While in receiving state, station at (x, y, z) (here x, y, z cannot equals to 1 at the same time) will always check whether it has received all the messages it can decode. If this station (x, y, z) finds that all the messages it can decode has been received, it will change its state to sending state, and its Sx, y, z equals to the maximum Sx, y, z value it had decoded plus one.
Now for coordinates (x, y, z), we want to know the sum of all the messages sent from stations (x', y', z'). Here 1 ≤ x' ≤ x, 1 ≤ y' ≤ y, 1 ≤ z' ≤ z.
There are at most 100000 test cases, each test case in a line, each line contains three integers x, y and z. Here 1 ≤ x, y, z ≤ 500000.
For each testcase, you should output the sum of all messages sent from stations whose coordinates (x', y', z') fulfill 1 ≤ x' ≤ x, 1 ≤ y' ≤ y, 1 ≤ z' ≤ z in one line.
2 2 2 2 3 2 2 1 3 5 3 4
20 32 13 220
Author: FAN, Yuzhe
Contest: ZOJ Monthly, February 2011