矩阵乘法快速幂 codevs 1250 Fibonacci数列

codevs 1250 Fibonacci数列

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 钻石 Diamond

题目描述 Description

定义：f0=f1=1, fn=fn-1+fn-2(n>=2)。{fi}称为Fibonacci数列。

输入n，求fn mod q。其中1<=q<=30000。

输入描述 Input Description

第一行一个数T(1<=T<=10000)。

以下T行，每行两个数，n，q(n<=109, 1<=q<=30000)

输出描述 Output Description

文件包含T行，每行对应一个答案。

样例输入 Sample Input

6 2

7 3

7 11

样例输出 Sample Output

数据范围及提示 Data Size & Hint

1<=T<=10000

n<=109, 1<=q<=30000

分类标签 Tags 点此展开

矩阵乘法数论

 1 #define N 3
 2 #include<iostream>
 3 using namespace std;
 4 #include<cstdio>
 5 #include<cstring>
 6 struct Jz{
 7     int cal,line;
 8     int jz[N][N];
 9 };
10 int q;
11 int read()
12 {
13     char s;
14     int ans=0,ff=1;
15     s=getchar();
16     while(s<'0'||s>'9')
17     {
18         if(s=='-') ff=-1;
19         s=getchar();
20     }
21     while('0'<=s&&s<='9')
22     {
23         ans=ans*10+s-'0';
24         s=getchar();
25     }
26     return ans*ff;
27 }
28 Jz martax(Jz x,Jz y)
29 {
30     Jz ans;
31     ans.line=x.line;
32     ans.cal=y.cal;
33     for(int i=1;i<=ans.line;++i)
34       for(int j=1;j<=ans.cal;++j)
35       {
36           ans.jz[i][j]=0;
37           for(int k=1;k<=x.cal;++k)
38           ans.jz[i][j]=(ans.jz[i][j]+x.jz[i][k]*y.jz[k][j])%q;
39       }
40     return ans;
41 }
42 int Fast_martax(int n)
43 {
44     if(n==0||n==1) return 1;
45     n--;
46     Jz ans,a;
47     a.cal=a.line=2;
48     a.jz[1][1]=0;a.jz[1][2]=1;
49     a.jz[2][1]=1;a.jz[2][2]=1;
50     ans.line=2;ans.cal=1;
51     ans.jz[1][1]=1;ans.jz[2][1]=1;
52     while(n)
53     {
54         if(n&1)
55         {
56             ans=martax(a,ans);
57         }
58         n>>=1;
59         a=martax(a,a);
60     }
61     return ans.jz[2][1]%q;
62 }
63 int main()
64 {
65     int T,n;
66     T=read();
67     while(T--)
68     {
69         n=read();q=read();
70         printf("%d
",Fast_martax(n));
71     }
72     return 0;
73 }