shunfurh
编程介的小学生
2017-09-29 13:20

Stern-Brocot Tree

  • 数据
  • c
  • 测试
  • 编程

Problem Description
  

  
  上图是一棵Stern-Brocot树,其生成规则如下:
  从第1行到第n行,每行相邻两数a/b和c/d,产生中间数(a+c)/(b+d),置于下一行中。将一行的分数(包括0/1,1/0),进行约分简化,则每一行(包括0/1,1/0,1/1),不会出现两个相同的分数。若分子或者分母大于n,则去掉该分数,将剩下的分数,从小到大排序,得到数列F。
  现在请您编程计算第n行的数列F的个数。

Input
  输入包含多组测试用例,每组输入数据是一个正整数n(n<=1000000)。

Output
  对于每组的测试数据n,请输出第n行的数列F的个数。

Sample Input
1
2
4
6

Sample Output
3
5
13
25

  • 点赞
  • 回答
  • 收藏
  • 复制链接分享

2条回答

为你推荐