HDU 4556 Stern-Brocot Tree

题目:点击打开链接

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

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » HDU 4556 Stern-Brocot Tree

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡