Such A Complex Formula
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 4 Accepted Submission(s) : 3
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
There are three kinds of operations for a given number x:
1. obtain the number 2*x from a number x;
2. obtain the number 2*x + 1 from a number x;
3. obtain the number floor(x/2) (the integer part of x divided by 2) from a number x.
For a pair of given positive integers (x, y), you should use the shortest sequence of operations above sufficient for obtaining the number y from the number x.
We define function S(x, y) as the number of operations in the shortest sequence.
1. obtain the number 2*x from a number x;
2. obtain the number 2*x + 1 from a number x;
3. obtain the number floor(x/2) (the integer part of x divided by 2) from a number x.
For a pair of given positive integers (x, y), you should use the shortest sequence of operations above sufficient for obtaining the number y from the number x.
We define function S(x, y) as the number of operations in the shortest sequence.
Input
There are multiple test cases. The first line contains an integer T (T<=30), indicating the number of test cases.
Then follows T lines, each line contains an integer n (2<=n<=10^18).
Then follows T lines, each line contains an integer n (2<=n<=10^18).
Output
For each test case, output "Case #D: " first, D is the test case number and then you have to calculate
and output this number modulus 10^9+7.
and output this number modulus 10^9+7.
Sample Input
2 2 3
Sample Output
Case #1: 4 Case #2: 48
Source
华南师范大学·2012年ACM程序设计竞赛·决赛