原題： The fibonacci number is defined by the following recurrence: ? fib(0) = 0 ? fib(1) = 1 ? fib(n) = fib(n ? 1) + fib(n ? 2) But we’re not interested in the fibonacci numbers here. We would like to know how many calls does it take to evaluate the n-th fibonacci number if we follow the given recurrence. Since the numbers are going to be quite large, we’d like to make the job a bit easy for you. We’d only need the last digit of the number of calls, when this number is rePResented in base b. Input Input consists of several test cases. For each test you’d be given two integers n (0 ≤ n < 2 63 ? 1), b (0 < b ≤ 10000). Input is terminated by a test case where n = 0 and b = 0, you must not process this test case. Output For each test case, print the test case number first. Then print n, b and the last digit (in base b) of the number of calls. There would be a single space in between the two numbers of a line. Note that the last digit has to be represented in decimal number system. Sample Input 0 100 1 100 2 100 3 100 10 10 0 0 Sample Output Case 1: 0 100 1 Case 2: 1 100 1 Case 3: 2 100 3 Case 4: 3 100 5 Case 5: 10 10 7

中文： 問(wèn)你求第n個(gè)斐波那契數(shù)時(shí)，要調(diào)用多少次斐波那契函數(shù)（線性），結(jié)果取b的模。

思路：

調(diào)用多少次函數(shù)的公式為 fib(i)=fib(i-1)+fib(i-2)+1

因?yàn)槭侨的模，而b的值在10000以?xún)?nèi)，也就是會(huì)出現(xiàn)循環(huán)節(jié) 如果是取模的話(huà) fib(i)=(fib(i-1)+fib(i-2)+1)%b 找到fib(i-1)=1且fib(i)=1時(shí)的i-1值，就是當(dāng)前的循環(huán)節(jié)。提前打個(gè)表保存一下即可，也可以把這個(gè)循環(huán)節(jié)里面的所以數(shù)都算出來(lái)打表，更加方便。