大数斐波那契取模模板
发布时间:2020-12-14 02:38:29 所属栏目:大数据 来源:网络整理
导读:大数斐波那契取模: #include cstdio#include cstring#include iostreamusing namespace std;const int mod=19999997;typedef struct{ long long m[2][2];}matrix;matrix I={1,1};matrix P={0,1,1};matrix mul(matrix a,matrix b){ int i,j,k; matrix c; for
大数斐波那契取模:
#include <cstdio> #include <cstring> #include <iostream> using namespace std; const int mod=19999997; typedef struct { long long m[2][2]; }matrix; matrix I={1,1}; matrix P={0,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("%dn",(temp.m[1][0]+temp.m[1][1])%mod); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |