#P2609. [ZJOI2012] 数列

    ID: 1617 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>数论数学高精度2012各省省选递归浙江

[ZJOI2012] 数列

题目描述

小白和小蓝在一起上数学课,下课后老师留了一道作业,求下面这个数列的通项公式:

a0=0,a1=1,a2i=ai,a2i+1=ai+ai+1a_0=0,a_1=1,a_{2i}=a_i,a_{2i+1}=a_i+a_{i+1}

小白作为一个数学爱好者,很快就计算出了这个数列的通项公式。于是,小白告诉小蓝自己已经做出来了,但为了防止小蓝抄作业,小白并不想把公式公布出来。于是小白为了向小蓝证明自己的确做出来了此题以达到其炫耀的目的,想出了一个绝妙的方法:即让小蓝说一个正整数 nn,小白则说出 ana_n 的值,如果当 nn 很大时小白仍能很快的说出正确答案,这就说明小白的确得到了公式。但这个方法有一个很大的漏洞:小蓝自己不会做,没法验证小白的答案是否正确。作为小蓝的好友,你能帮帮小蓝吗?

输入格式

输入文件第一行有且只有一个正整数 TT,表示测试数据的组数。

接下来 TT 行,每行一个整数 nn

输出格式

对于每组数据:输出一行一个整数代表 ana_n

3
1
3
10
1
2
3

提示

  • 对于 20%20\% 的数据,1n1081 \le n \le 10^8
  • 对于 50%50\% 的数据,1n10121 \le n \le 10^{12}
  • 对于 100%100\% 的数据,1T201 \le T \le 201n101001 \le n \le 10^{100}