Welcome   HUNAN NORMAL UNIVERSITY ACM/ICPC Judge Online
Home
FAQs
Problem Set
Practices
Online Contests
Major Exercises
OI Special
Judgement
Submit
Online Status
User Ranklist
Users
Register new
Login
Web Links
Hunan Normal University
College of Information Science and Engineering
考拉兹猜想
Time Limit: 5000ms, Special Time Limit:5000ms, Memory Limit:32768KB
Total submit users: 25, Accepted users: 7
Problem 11850 : No special judgement
Problem description
  考拉兹猜想,英文称作Collatz conjecture,还拥有其他众多的名字,如:Ulam conjecture, Kakutani problem, Thwaites conjecture, Hasse’s algorithm, Syracuse problem, 3n+1 conjecture, 等。
好吧,当你看到最后一个名称时,你可能已经知道这是什么东西了。给定一个正整数n,如果n是奇数就把它乘3加1,如果n是偶数就把它除以2,如此反复,最后必定能得到1。这就是考拉兹猜想的内容。
例如第一个数取5,则可以依次得到:16, 8, 4, 2, 1。如果我们称{5,16,8,4,2,1}是5的考拉兹数列。任意给定正整数a和b,问a的考拉兹数列和b的考拉兹数列的最长公共子序列的长度是多少。

Input
  首先是一个不超过10000000的正整数n,表示其后有n对数。然后是n对正整数,每一对记作a和b。a、b均不超过100000。

Output
  对每一对数,输出一行为答案。

Sample Input
1
5 4
Sample Output
3
Judge Tips
  5和4的考拉兹数列分别是{5,16,8,4,2,1}和{4,2,1},所以答案是3。

Problem Source
  HUNNU Contest 

Submit   Discuss   Judge Status  Problems  Ranklist 

HUNAN NORMAL UNIVERSITY ACM/ICPC Judge Online, Version 2010.5.5.final.
Web visits:19182 today,16242173 total, since 2010-05-07