UVA 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[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.e-learn.cn/content/qita/2190529

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
const int inf=10003;
int jj[inf];
void euler()
{
for (int i=1;i<=inf;i++)
jj[i]=i;
for(int i=2;i<inf;i++){
if(jj[i]==i)
for(int j=i;j<inf;j+=i){
jj[j]=jj[j]/i*(i-1);
}
jj[i]+=jj[i-1];//
}
}
int main()
{
int n,k,x,a[10010];
cin>>n;
euler();
for(int i=1;i<=15;i++){
cout<<jj[i]<<" ";
}
while(n--)
{
scanf("%d%d",&k,&x);
cout<<k<<" "<<jj[x]*3-1<<"/2"<<endl;
}
return 0;
}