【费马小定理+矩阵快速幂】HDU4549——M斐波那契数列

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 typedef long long ll;
 7 const ll MOD=1000000007;
 8 int a,b,n;
 9 
10 void mul(ll A[][2],ll B[][2])
11 {
12     ll C[2][2];
13     memset(C,0,sizeof(C));
14     for (int i=0;i<2;i++)
15         for (int j=0;j<2;j++)
16             for (int k=0;k<2;k++) 
17                 C[i][j]=(C[i][j]+A[i][k]*B[k][j])%(MOD-1);
18     for (int i=0;i<2;i++)
19         for (int j=0;j<2;j++) B[i][j]=C[i][j];
20 }
21 
22 void fibonacci(ll &fa,ll &fb)
23 {
24     ll acc[2][2]={{1,1},{1,0}};
25     ll now[2][2]={{1,0},{0,1}};
26     int res=n-1;
27     while (res>0)
28     {
29         if (res&1) mul(acc,now);
30         mul(acc,acc);
31         res>>=1;
32     }
33     fa=now[0][1];
34     fb=now[0][0];
35 }
36 
37 ll get_ans(ll x,ll p)
38 {
39     ll now=x;
40     ll res=p;
41     ll ret=1;
42     while (res>0)
43     {
44         if (res&1!=0) ret=(ret*now)%MOD;
45         now=(now*now)%MOD;
46         res>>=1;
47     }
48     return ret;
49 }
50 
51 int main()
52 {
53     while (~scanf("%d%d%d",&a,&b,&n))
54     {
55         if (n==0) cout<<a<<endl;
56         else if (n==1) cout<<b<<endl;
57         else
58         {
59             ll fa=0,fb=0;
60             fibonacci(fa,fb);
61             printf("%lld
",(get_ans(a,fa)*get_ans(b,fb))%MOD); 
62         }
63     }
64     return 0;
65 }