Charles Frédéric Gros (CFG) has decided to disprove the Riemann hypothesis numerically. For a given integer D > 0 of the form 4k + 3 and free of square prime factors, this amounts to computing the cardinality h(D) of the set def 2 C(D) = {(a,b,c)|b −4ac=−D,|b|≤a≤c, whereb≥0ifa=cora=|b|. (Where a, b, c are integers.) For instance, C (3) = {(1, 1, 1)}, C (15) = {(1, 1, 4), (2, 1, 2)}. Note that D = 75 is not eligible, since 75 = 3 · 52. Non-eligible numbers in the interval [3, 103] are {27, 63, 75, 99}. √ CFG is interested in values of D for which h(D)/ D is large. Your role is to write a program to help CFG finding these record numbers. Input You are given an input file consisting of several test cases, each of them consists of three integers on a single line: Dmin Dmax K where 3 ≤ Dmin ≤ Dmax < 231 and are of the form 4k+3. Moreover, Dmax−Dmin ≤ 106 and K < 104. For such values, one has h(D) < 231. Output For each test case, your program must determine the eligible values of D in the interval [Dmin, Dmax] for which ⌊√⌋ f(D) = (1000 h(D))/⌊ D⌋ ≥ K. The output will consist of lines: Dhf where D is a record number, h = h(D) and f = f(D). If no answer is found, then output a line containing the word ‘empty’. Write a blank line to separate the output of two consecutive cases. Sample Input 3 103 0 27 27 10 Sample Output 3 1 1000 7 1 500 11 1 333 15 2 666 19 1 250 23 3 750 31 3 600
2/2 35 2 400 39 4 666 43 1 166 47 5 833 51 2 285 55 4 571 59 3 428 67 1 125 71 7 875 79 5 625 83 3 333 87 6 666 91 2 222 95 8 888 103 5 500 empty