HDU 4556 Stern-Brocot Tree
栏目：php教程时间：2016-09-25 09:01:19
题目：点击打开链接
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的个数。
Input
输入包括多组测试用例，每组输入数据是1个正整数n（n<=1000000）。
Output
对每组的测试数据n，请输出第n行的数列F的个数。
Sample Input
1
2
4
6
Sample Output
3
5
13
25
这个题目就是想说明，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;
}
------分隔线----------------------------
上一篇 面向对象的原则之单一职责原则
下一篇 十分钟玩转泛型
------分隔线----------------------------