1028. Hanoi Tower Sequence

Description

Hanoi Tower is a famous game invented by the French mathematician Edourard Lucas in 1883. We are given a tower of n disks, initially stacked in decreasing size on one of three pegs. The objective is to transfer the entire tower to one of the other pegs, moving only one disk at a time and never moving a larger one onto a smaller.

The best way to tackle this problem is well known: We first transfer the n-1 smallest to a different peg (by recursion), then move the largest, and finally transfer the n-1 smallest back onto the largest. For example, Fig 1 shows the steps of moving 3 disks from peg 1 to peg 3.

Now we can get a sequence which consists of the red numbers of Fig 1: 1, 2, 1, 3, 1, 2, 1. The ith element of the sequence means the label of the disk that is moved in the ith step. When n = 4, we get a longer sequence: 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1. Obviously, the larger n is, the longer this sequence will be.
Given an integer p, your task is to find out the pth element of this sequence.

Input

The first line of the input file is T, the number of test cases.
Each test case contains one integer p (1<=p<10^100).

Output

Output the pth element of the sequence in a single line. See the sample for the output format.
Print a blank line between the test cases.

Sample Input

Copy sample input to clipboard

4
1
4
100
100000000000000

Sample Output

Case 1: 1
 
Case 2: 3
 
Case 3: 3
 
Case 4: 15

分析：
1:    1
2:    121
3:    1213121
4:    121312141213121
5:    1213121412131215121312141213121
6:    121312141213121512131214121312161213121412131215121312141213121
7:    1213121412131215121312141213121612131214121312151213121412131217121312141213121512131214121312161213121412131215121312141213121
从上面可以看出，第 K 个数的值就是 K 能被 2 整除的次数 + 1，那么可以用求模的方法来做。因为是大整数，所以用字符串来表示数，用如下的算法来求得模后的值：
12345678901234567890 % m
1 % m = 1
12 % m = (1 * 10 + 2) % m = (1 % m * 10 + 2) % m
123 % m = (12 * 10 + 3) % m = (12 % m * 10 + 3) % m
…
12345678901234567890 % m
= ( ( 1 % m * 10 + 2 ) % m*10+3 ) % m …

另外就是除于 2，这个很好弄，因为除数是已知的，那么除完以后的结果最多比原 string 少一个元素，就是头元素变为 '0'，只要判断这个就可

#include <iostream>

using namespace std;

int modFunction(string& num) {
    int len = num.size();
    int pre = 0;
    int current;
    int i = 0;
    while (i < len) {
        current = pre * 10 + num[i] - '0';
        pre = current % 2;
        current /= 2;
        num[i++] = current + '0';  // 除于 2 的结果
    }
    if (num[0] == '0')
        num = num.substr(1, len);  // 原来的第一个元素是否是 1
    return pre;
}

int main(int argc, char const *argv[])
{
    int testNum;
    cin >> testNum;
    int caseNum = 0;
    string number;
    while (caseNum++ < testNum) {
        if (caseNum != 1)
            cout << endl;
        cin >> number;
        int num = 0;
        while (modFunction(number) == 0) {
            ++num;
        }
        cout << "Case " << caseNum << ": " << num + 1 << endl;
    }

    return 0;
}