感觉每次网络赛刚开始总是像打了鸡血一样，斗志满满，不过不出3个小时，斗志就被自己的渣渣实力所消磨了，像前两场比赛一样，这场比赛也是有些困难。

刚开始做了三个水题之后，就是一路卡了。不过呢，队里的大牛还是刷出了第四题，让我印象最深的还是其中的一个数学题了，题目大概是这样的：现在已经在了http://acm.hdu.edu.cn/showproblem.php?pid=5451

Best Solver

Time Limit: 1500/1000 MS (Java/Others) Memory Limit: 65535/102400 K (Java/Others) Total Submission(s): 295 Accepted Submission(s): 129

Problem Description

The so-called best problem solver can easily solve this problem, with his/her childhood sweetheart.

It is known that

y=(5+26√)1+2x

.

For a given integer

x (0≤x<232)

and a given prime number

M (M≤46337)

, print

[y]%M

. (

[y]

means the integer part of

y

)

Input

An integer

T (1

, indicating there are

T

test cases.

Following are

T

lines, each containing two integers

x

and

M

, as introduced above.

Output

The output contains exactly

T

lines.

Each line contains an integer representing

[y]%M

.

Sample Input

7

0 46337

1 46337

3 46337

1 46337

21 46337

321 46337

4321 46337

Sample Output

Case #1: 97

Case #2: 969

Case #3: 16537

Case #4: 969

Case #5: 40453

Case #6: 10211

Case #7: 17947

当时一看惊呆了，2的2的32次方，那不是飞起来了吗，想了很久还是惊呆了。最终还是没做出来。。。。

最后感觉还是差了一题，没拿到现场赛的资格，还是要努力啊！

题解先摆在这，日后补上这题的代码！！

1002.Best solver

Degree of Difficulty (0~10)：3 Category：Algebra

There exists a sequence F(n+2)=a\times F(n+1)+b\times F(n)F(n+2)=a×F(n+1)+b×F(n) such that 5+2\times \sqrt{6}5+2×√​6​​​ is an eigenvalue of it. Therefore the problem is converted to compute the power of a 2-order matrix. On the other hand, invertible matrices in Zp form a group of order (p^2- p)(p^2-1)p​2​​−p)(p​2​​−1). Thus we have a period of the power of matrix. The time complexity is O(log^2(n))O(log​2​​(n)).