ZOJ Problem Set - 3428
Two species of bugs, Red iNT and Green fLOAT, are living in Blue Matrix. They have a race at Code Cube every four years. Code Cube is a cuboid with integer dimensions. Bugs will run from the corner of Code Cube to the opposite corner in the race, choosing the shortest route. However, Red iNT can only run on the surfaces of the cuboid, and the shortest distance it runs is always an integer. Green fLOAT can run inside the cuboid, and the shortest distance it runs may be any real number. The race seems to be unfair, but iNT runs much more faster than fLOAT, so both have chance to win.
The scale of a Code Cube is defined as the maximum dimension of it. There are two different minimum cuboids satisfying the requirements above, 2×2×3 and 1×3×3, where the distances of Red iNT's routes are both 5 and the distances of Green fLOAT's routes are sqrt(17) and sqrt(19). Of course, the distances vary from one cuboid to another cuboid. Now the problem comes that bugs want to know the mean squared distances for all cuboids with the same scale.
The input contains thousands of lines of integers n, which indicates the scale of Code Cube. n will be between 1 and 1000000, inclusive.
Output the mean squared distance Red iNT runs and the one Green fLOAT runs as irreducible fraction, or "NaN" if both the numerator and the denominator are zero. See sample for more details.
1 2 3 4 1000
NaN NaN NaN NaN 25/1 18/1 25/1 21/1 220986875/114 538411225/342
Author: WU, Zejun
Contest: ZOJ Monthly, November 2010