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[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

题意:
输入x,列出0~1之间所有的分母从1到x的分数,然后将分数从小到到排序,分母依次为b[1],b[2],b[3],……,b[k]。计算b[i]/b[i+1]的总和。

题解:
https://blog.csdn.net/nameofcsdn/article/details/52597478
分子:欧拉函数的前n项和(不包含1) * 3 + 2
分母:始终为2

代码:

#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;
}

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注