
ZOJ Problem Set  3843
William thinks 89 is an unlucky number for him. But he still wants to know more about 89. He knows 89 is the 24th prime number, and also a Fibonacci number after searching on the internet. Recently, William starts to study some problems about right triangles. He call a right triangle is unlucky if lengths of its both legs are integers and the length of the hypotenuse is a multiple of √89. For example, a right triangle with three edges (5,8,√89) is unlucky, (4,47,5√89), (17,44,5√89), and (10,16,2√89) are also unlucky. He thinks each unlucky triangle has an energy which is defined by its hypotenuse. The energy of an unlucky triangle is its hypotenuse divided by √89. For example, the energy of (5,8,√89) is 1, and the energy of (71,100,13√89) is 13. William is very curious about the average circumference of all the unlucky triangles whose energy is less than or equal to n. The circumference of a triangle is the sum of its three sides. Can you help him? William is expecting a precise answer. InputThere are multiple cases. Each case is an integer number n in a line. (1≤ n≤ 10^{8}, the sum of n in the whole input is less than 2*10^{8}) OutputEach output for one case has 5 lines. Each output should be in the following format: *************************************************** * Numerator1 Numerator2 __* *Integer1 + Integer2 x V89* * Denominator1 Denominator2 * ***************************************************Each mixed fraction should be irreducible. When numerator is 0, the proper fraction part should be omitted. If Numerator2 is 0 and Integer2 is 1, then "1 x " part should be omitted too. The numerator and the denominator need to be rightaligned. The "" part should be as same long as the corresponding denominator. Note the characters other than digits used in the output: '*'(Asterisk, ascii code 42), ' '(Space, ascii code 32), '_'(Underscore, ascii code 95), ''(Hyphen or minus sign, ascii code 45), 'x'(letter x, ascii code 120), and 'V'(letter V, ascii code 86). Print a blank line after each case. Please refer to the sample output. Sample Input1 8 9 89 99999999 Sample Output********** * __* *13 + V89* * * ********** *************** * 3 __* *58 + 4 x V89* * 5 * *************** **************** * 4 __* *63 + 5 x V89* * 11 * **************** ******************** * 37 13 __* *598 + 48 x V89* * 90 18 * ******************** ********************************************** * 93224754 97600661 __* *620114538 + 51235071 x V89* * 106191655 318574965 * ********************************************** HintIf n is 10^{8}, there are 637149947 kinds of right triangles in different shapes and sizes. Explanation for n=8, we can find 10 unlucky right triangles whose energy is no more than 8. They are (5,8,√89), (10,16,2√89), (15,24,3√89), (20,32,4√89), (4,47,5√89), (17,44,5√89), (25,40,5√89), (30,48,6√89), (35,56,7√89), and (40,64,8√89). The sum of circumferences is 580+46√89, so the average circumference is (580+46√89)/10. Author: ZHOU, Yuchen Source: ZOJ Monthly, January 2015 