1018.txt

厦门大学OJ上的ACM题1018源码

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;   
}