1018.零零漆的作業
Time Limit: 1000 MS         Memory Limit: 65536 K 
Total Submissions: 482 (106 users)         Accepted: 110 (61 users) 
[ My Solution ] 

Description
　　　世上沒有鐵飯碗, 裁員風也刮到了組織, 盡管零零漆為組織做了那么多貢獻, 他還是得通過組織的素質能力以及水平測試才能繼續他的特工工作. 憑他的經驗以及高超的殺豬功力, 他順利的通過了前面的測試, 來到了算法測試關. 給他的問題很簡單----給兩個整數n,m, 求斐波納契數fib[n] % m...
算賣肉錢久了, 零零漆還真想不起怎么去計算斐波納契數了, 但是他在考場竟然能通過安裝在皮鞋里的電話和你通信, 他只能寄希望于你了...
當然你還是知道fib[n]的定義的:
/ fib[0]=0
| fib[1]=1
\ fib[n]=fib[n-1]+fib[n-2] (n>1)



Input
　　　輸入第一行是一個整數 c, 0 < c <= 5000, 表示要計算多少個fib[n]
接下來的c行, 每行有兩個整數n,m, 0 <= n <= 2147483647, 0 < m < 32767, 意義如前所述



Output
　　　對于每對n,m, 對應輸出單獨的一行, 包含一個整數 r = fib[n] % m



Sample Input
8
42 8468
6335 6501
19170 5725
11479 9359
26963 4465
5706 8146
23282 6828
9962 492



Sample Output
3712
3547
1210
5683
1502
5894
5113
1





RunId 28490 of Problem 1018
Submit Time: 2008-10-29 00:58:02    Language: G++    Code Length: 1263 B 
   Result: Accepted    Time: 188 MS    Memory: 48 K    Judge: Apple



#include <stdio.h>   
#define MAX 80   
typedef struct record{   
    long mark;   
    long n1, n2;   
    long m1, m2;   
}record;   
record p[MAX+1];   
record* calc(long n, int m)   
{   
    if (n == 1){   
        int flag;   
        for (int i=1; i<=MAX; i++)   
            if (p[i].mark == 0){   
                flag = i;   
                break;   
            }   
            else if (p[i].mark == 1)   
                return &p[i];   
        p[flag].n1 = 0;   
        p[flag].n2 = 1;   
        p[flag].m1 = 1;   
        p[flag].m2 = 1;   
        p[flag].mark = 1;   
        return &p[flag];   
    }   
    record* q;   
    for (int i=1; i<=MAX; i++)   
        if (p[i].mark == n)   
            return &p[i];   
        else if (p[i].mark == 0){   
            q = &p[i];   
            q->mark = n;   
            break;   
        }   
    record* q1 = calc(n/2, m);   
    record* q2 = calc(n-n/2, m);   
    q->n1 = (q1->n1 * q2->n1 + q1->n2 * q2->m1) % m;   
    q->m1 = (q1->m1 * q2->n1 + q1->m2 * q2->m1) % m;   
    q->n2 = (q1->n1 * q2->n2 + q1->n2 * q2->m2) % m;   
    q->m2 = (q1->m1 * q2->n2 + q1->m2 * q2->m2) % m;   
    return q;   
}   
int main()   
{   
    int c;   
    scanf("%d", &c);   
    for (int i=1; i<=c; i++){   
        for (int j=1; j<=MAX; j++)   
            p[j].mark = 0;   
        long n;   
        int m;   
        scanf("%ld %d", &n, &m);   
        if (n == 0){   
            printf("0\n");   
            continue;   
        }   
        if (n == 1){   
            printf("%d", 1%m);   
            continue;   
        }   
        record* result = calc(n-1, m);    
        printf("%d\n", result->m2);   
    }   
    return 0;   
}