Collatz问题

Time Limit: 250 ms Memory Limit: 65536 KiB

Problem Description

一下迭代序列定义在整数集合上:

n = n/2 (n 是偶数)

n = n*3 + 1(n 是奇数)

应用以上规则,并且以数字13开始我们得到一下序列:

13,40,20,10,5,16,8,4,2,1

可以看出这个以13开始以1结束的序列一共经过了9次运算。虽然还没有被证明(Collatz问题),但是人们认为在这个规则下,以任何数字开始都会以结束。

 

以哪个不超过x的正整数开始,能得到运算次数最多的序列?

注意:一旦序列开始,也就是从第二项开始,项是可以超过x的。

Input

 

输了一个整数n,接下来n行,每行一个整数x (1 <=x<=1,000,000)

Output

 

对于每次询问,你需要计算出最多的运算次数是多少。为了节约输出时间,你只需要输出所有询问的答案之和 。

Sample Input

3
1
2
3

Sample Output

8

Hint

 

因为测试数据过大,建议使用高效的读入,比如scanf()

如果你觉得scanf()仍然不够快,可以参考一下读入方式。

 

#include 

 

template 

inline void read(T& x) {

    char ch; while (!((((ch=getchar())>='0') && (ch <= '9')) || (ch == '-')));

    x = ch-'0'; while (((ch=getchar())>='0') && (ch <= '9')) x = x*10+ch-'0';

}

 

int main()

{

    int a,b;

    read(a);//等价于scanf(“%d”,&a);

    read(b);//等价于scanf(“%d”,&b);

}

Source