Stern-Brocot Tree
TimeLimit:1000MS MemoryLimit:32768KB
64-bit integer IO format:%I64d
未提交 | 登录后收藏
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的个数。
SampleInput
1 2 4 6
SampleOutput
3 5 13 25