hdu 4549(快速幂）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4549

思路：大牛思路：简单推导下有, a, b, a^1*b^1, a^1*b^2 .... 可以知道a,b的幂满足Fib, 然后构造矩阵快速幂...就好了.还需要个性质: A^X = A^( X mod Eular(M) ) ( mod M ) .

然后我就郁闷啦，自己的代码怎么都过不了，orz...

一下是wa代码，哪个大神帮忙看看：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 #define MOD 1000000007
 7 typedef long long ll;
 8 struct Matrix{
 9     ll map[2][2];
10 };
11 Matrix Mata,Unit;
12 
13 
14 void Initaite(){
15     Unit.map[0][0]=Unit.map[1][1]=1;
16     Unit.map[0][1]=Unit.map[1][0]=0;
17 
18     Mata.map[0][0]=0;
19     Mata.map[0][1]=1;
20     Mata.map[1][0]=1;
21     Mata.map[1][1]=1;
22 }
23 
24 Matrix Mul(const Matrix &p,const Matrix &q){
25     Matrix r;
26     memset(r.map,0,sizeof(r.map));
27     for(int i=0;i<2;i++){
28         for(int j=0;j<2;j++){
29             for(int k=0;k<2;k++){
30                 r.map[i][j]=(r.map[i][j]+p.map[i][k]*q.map[k][j])%(MOD-1);
31             }
32         }
33     }
34     return r;
35 }
36 
37 Matrix Pow(int n){
38     Matrix q=Unit,p=Mata;
39     while(n){
40         if(n&1){
41             q=Mul(p,q);
42         }
43         n>>=1;
44         p=Mul(p,p);
45     }
46     return q;
47 }
48 
49 ll PPow(ll x,ll n){
50     ll p=x,q=1;
51     while(n){
52         if(n&1){
53             q=p*q%MOD;
54         }
55         n>>=1;
56         p=p*p%MOD;
57     }
58     return q;
59 }
60 
61 
62 int main(){
63     Initaite();
64     int a,b,n;
65     while(~scanf("%d%d%d",&a,&b,&n)){
66         if(n==0)printf("%d\n",a);
67         else if(n==1)printf("%d\n",b);
68         else {
69             Matrix Mat1=Pow(n-1);
70             ll x1=Mat1.map[1][1],x2=Mat1.map[0][1];
71         //    cout<<x1<<x2<<endl;
72             ll ans=PPow(a,x1)*PPow(b,x2)%MOD;
73            printf("%d\n",(int)ans);
74         }
75     }
76     return 0;
77 }

View Code