陕西师范大学第七届程序设计竞赛网络同步赛 J 黑猫的小老弟【数论/法拉数列/欧拉函数】

链接：https://www.nowcoder.com/acm/contest/121/J
来源：牛客网

题目描述

大家知道，黑猫有很多的迷弟迷妹，当然也有相亲相爱的基友，这其中就有一些二五仔是黑猫的小老弟。小老弟是如何产生的呢？聪明的iko告诉黑猫，其实是有规律的（她怎么知道？？？）！

一开始，有两个原始二五仔，代号0/1和1/1，

从原始二五仔到第n代小老弟，每代相邻两个小老弟a/b和c/d，产生一个新的小老弟(a+c)/(b+d)，成为下一代新成员。将每一代的小老弟代号约分（包括0/1,1/1），进行约分简化，则每一代的代号（包括0/1,1/1），不会出现两个相同的分数。若分子或者分母大于n，则去掉该代号，将剩下的分数，从小到大排序，得到小老弟名单数列F。

现在，黑猫为了让这些小老弟往后稍稍，请您编程计算第n代的名单数列F的个数。

输入描述:

先输入一个数t，然后t组数据，每行一个数字n（n<10000）

输出描述:

输出第n代名单有多少人。

输入例子:

2

1

4

输出例子:

2

7

-->

示例1

输入

2

1

4

输出

2

7

示例2

输入

3

8803

9017

8370

输出

23559251

24718873

21296477

【分析】：可以发现，这棵树从中间分开，就是法里数列！法里数列长度f[n]=f[n-1]+φ(n)

法里数列：

Farey数列Fn对于每个n( n>=2 ),如果0<a<b<=n 且 ab互质即a/b为不可约有理数，那么就在Fn集合中且以递增序列排序。
F2 ={1/2} 
F3 = {1/3, 1/2, 2/3} 
F4 = {1/4, 1/3, 1/2, 2/3, 3/4} 
F5 = {1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5}

欧拉函数：

在数论，对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目（φ(1)=1）。

#include<bits/stdc++.h>

#include<cstdio>

#include<string>

#include<cstdlib>

#include<cmath>

#include<iostream>

#include<cstring>

#include<set>

#include<queue>

#include<algorithm>

#include<vector>

#include<map>

#include<cctype>

#include<stack>

#include<sstream>

#include<list>

#include<assert.h>

#include<bitset>

#include<numeric>

#define debug() puts("++++")

#define gcd(a,b) __gcd(a,b)

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define fi first

#define se second

#define pb push_back

#define sqr(x) ((x)*(x))

#define ms(a,b) memset(a,b,sizeof(a))

#define sz size()

#define be begin()

#define pu push_up

#define pd push_down

#define cl clear()

#define lowbit(x) -x&x

#define all 1,n,1

#define rep(i,n,x) for(int i=(x); i<(n); i++)

#define in freopen("in.in","r",stdin)

#define out freopen("out.out","w",stdout)

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

typedef pair<int,int> P;

const int INF = 0x3f3f3f3f;

const LL LNF = 1e18;

const int maxn = 1e3 + ;

const int maxm = 1e6 + ;

const double PI = acos(-1.0);

const double eps = 1e-;

const int dx[] = {-,,,,,,-,-};

const int dy[] = {,,,-,,-,,-};

const int mon[] = {, , , , , , , , , , , , };

const int monn[] = {, , , , , , , , , , , , };

int n,k,t;

int e[maxm];

int sum[maxm],res = ;

void init()

{

    ms(e,);

    e[]=;

    for(int i=;i<=maxm;i++){

        if(!e[i])

        for(int j=i;j<=maxm;j+=i){

            if(!e[j])

                e[j]=j;

            e[j]=e[j]/i*(i-);

        }

    }

}

int main()

{

    init();

    sum[]=;

    for(int i=;i<=maxm;i++)

        sum[i]=sum[i-]+e[i]; //可以发现，这棵树从中间分开，就是法里数列~法里数列长度f[n]=f[n-1]+φ(n)

    cin>>t;

    while(t--)

    {

        cin>>n;

        cout<<sum[n]<<endl;

    }

}