HDU 4556 Stern-Brocot Tree
来源：程序员人生 发布时间：2016-09-25 09:01:19 阅读次数：2851次
题目：点击打开链接
Description
上图是1棵Stern-Brocot树，其生成规则以下：
从第1行到第n行，每行相邻两数a/b和c/d，产生中间数(a+c)/(b+d)，置于下1行中。将1行的分数（包括0/1,1/0），进行约分简化，则每行（包括0/1,1/0,1/1），不会出现两个相同的分数。若份子或分母大于n，则去掉该分数，将剩下的分数，从小到大排序，得到数列F。
现在请您编程计算第n行的数列F的个数。
Output
对每组的测试数据n，请输出第n行的数列F的个数。
这个题目就是想说明，SB树和Farey序列的关系。
代码就几近不用再写了，直接把我的博客略改便可。
代码：
#include<iostream>
#include<stdio.h>
using namespace std;
long long phi[1000001];
void get_phi()
{
for (int i = 1; i <= 1000000; i++)phi[i] = i;
for (int i = 2; i <= 1000000; i++)
{
if (phi[i] == i)for (int j = i; j <= 1000000; j += i)phi[j] = phi[j] / i*(i - 1);
phi[i] += phi[i - 1];
}
}
int main()
{
get_phi();
int n;
while (scanf("%d",&n)!=-1)printf("%llu\n", phi[n]*2+ 1);
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
