Stern-Brocot Tree

Time Limit: 3000/1000 MS (Java/Others)

Memory Limit: 65535/32768 K (Java/Others)

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

Hint

liuyiding

Source

2013金山西山居创意游戏程序挑战赛——初赛(4)

提交代码