题目描述
Given a positive integer, N, the sequence of all fractions a/b with (0 < a ≤ b), (1 < b ≤ N) and a and b relatively prime, listed in increasing order, is called the Farey Sequence of order N.
For example, the Farey Sequence of order 6 is:*0/1, 1/6, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 5/6, 1/1 *
If the denominators of the Farey Sequence of order N are: b[1], b[2], . . . , b[K]
then the Farey Sum of order N is the sum of b[i]/b[i + 1] from i = 1 to K—1.
For example, the Farey Sum of order 6 is:*1/6 + 6/5 + 5/4 + 4/3 + 3/5 + 5/2 + 2/5 + 5/3 + 3/4 + 4/5 + 5/6 + 6/1 = 35/2 *
Write a program to compute the Farey Sum of order N (input).
输入
The first line of input contains a single integer P, (1 ≤ P ≤ 10000), which is the number of data sets that follow. Each data set should be processed identically and independently.
Each data set consists of a single line of input. It contains the data set number, K, followed by the order N, (2 ≤ N ≤ 10000), of the Farey Sum that is to be computed.
输出
For each data set there is a single line of output. The single output line consists of the data set number,K, followed by a single space followed by the Farey Sum as a decimal fraction in lowest terms. If the denominator is 1, print only the numerator.
样例输入
4
1 6
2 15
3 57
4 9999
样例输出
1 35/2
2 215/2
3 2999/2
4 91180457/2
这一道题用模拟会T掉
正解是运用欧拉函数。
欧拉函数是用来计算N前有多少与N互质的数的方法。
想学习欧拉函数的可以看这里：https://www.elearn.cn/content/qita/2190529
1 
