http://blog.csdn.net/wust_xhj/article/details/47779539
怎么推可以看这里
f[0]=0
f[1]=1
[0,1]* | 0 q |(n-1)=[f(n-1),f(n)]
| 1 q-1|
跑一下快速幂
#include<stdio.h> #include<string.h> #include<algorithm> #include<math.h> using namespace std; typedef long long ll; #define MAXN 105 struct node { ll z[3][3]; }; ll Quick(ll a,ll b,ll c) { ll ans=1; while(b>0) { if(b%2==1) ans=(ans*a)%c; b/=2; a=(a*a)%c; } return ans; } ll p; node mou(node a,node b) { node c; for(int i=0;i<2;i++) { for(int j=0;j<2;j++) { ll sum=0; for(int k=0;k<2;k++) sum=(sum+a.z[i][k]*b.z[k][j])%p; c.z[i][j]=sum; } } return c; } int main() { ll x1,y1,z1,y2,z2; while(scanf("%lld%lld%lld",&x1,&y1,&z1)!=EOF) { if(x1==-1&&y1==-1&&z1==-1) break; scanf("%lld%lld%lld",&y2,&z2,&p); ll q=(Quick(x1,y1,p)+z1)%p; node s,a,ans; ans.z[0][0]=1; ans.z[0][1]=0; ans.z[1][0]=0; ans.z[1][1]=1; a.z[0][0]=0; a.z[0][1]=q; a.z[1][0]=1; a.z[1][1]=q-1; s=a; while(z2>0) { if(z2%2==1) ans=mou(ans,a); z2=z2/2; a=mou(a,a); } for(int i=0;i<y2;i++) { ans=mou(s,ans); s=mou(s,s); } printf("%d ",ans.z[1][1]); } return 0; }