大数斐波那契取模模板

2019-04-13 16:13发布

站内文章 / 模拟电子
14891 0 966
大数斐波那契取模： #include #include #include using namespace std; const int mod=19999997; typedef struct { long long m[2][2]; }matrix; matrix I={1,0,0,1}; matrix P={0,1,1,1}; matrix mul(matrix a,matrix b) { int i,j,k; matrix c; for(i=0;i<2;i++) for(j=0;j<2;j++) { c.m[i][j]=0; for(k=0;k<2;k++) c.m[i][j]+=(a.m[i][k]*b.m[k][j])%mod; c.m[i][j]%=mod; } return c; } matrix quick_mod(int n) { matrix a=P,b=I; while(n>0) { if(n&1) b=mul(b,a); n=n>>1; a=mul(a,a); } return b; } int main() { int n; while(scanf("%d",&n)!=-1) { matrix temp=quick_mod(n-1); printf("%d ",(temp.m[1][0]+temp.m[1][1])%mod); } return 0; }

热门文章