# H - Farey Sums

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, b, . . . , 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

https://blog.csdn.net/nameofcsdn/article/details/52597478

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const ll inf=0x3f3f3f3f;
const double pi=acos(-1.0);
const double eps=1e-8;
const double orea=0.57721566490153286060651209;
const int maxn=1e6+100;

int euler[maxn];

void initeuler()
{
for(int i=1;i<maxn;i++)
euler[i]=i;
for(int j=2;j<maxn;j++){
if(euler[j]==j){
for(int i=j;i<maxn;i+=j)
euler[i]=euler[i]/j*(j-1);
}
}

}

int main()
{
int n,k;
int num;
initeuler();
scanf("%d",&n);
while(n --)
{
ll sum = 0;
scanf("%d %d",&k ,&num);
for(int i=2;i<=num;i++)
sum+=euler[i];
printf("%d %lld/2\n",k, sum * 3  + 2);
}
return 0;
}