NOIP2017模拟赛 k-斐波（数学+欧几里得+矩阵乘法）

2019-04-14 17:40发布

站内文章 / 模拟电子
18058 0 1579
这里写图片描述 水题 复习 扩欧&矩阵乘法
扩欧注意最终取模！
关于数学的题如果没有超过空间那么尽量开longlong

代码

#include #include #include #include #include #include using namespace std; #define int long long typedef int arr[3][3]; arr a,ans,temp; int n,p; void cheng(arr a,arr b){ int i,j,k; memset(temp,0,sizeof(temp)); for(i=1;i<=2;i++){ for(j=1;j<=2;j++){ for(k=1;k<=2;k++){ temp[i][j]=(temp[i][j]+a[i][k]*b[k][j])%p; } } } memcpy(a,temp,sizeof(temp)); } int ksm(int y) { if(y==1||y==0) return 1; while(y) { if(y&1) cheng(ans,a); y>>=1; cheng(a,a); } return (ans[1][1]+ans[2][1])%p; } int gcd(int a,int b,int &x,int &y) { if(b==0){x=1;y=0;return a; } int r=gcd(b,a%b,x,y); int tmp; tmp=x;x=y;y=tmp-a/b*y; return r; } main() { // freopen("kfib.in","r",stdin); // freopen("kfib.out","w",stdout); int i,j; ans[1][1]=ans[2][2]=1; a[1][2]=a[2][1]=a[2][2]=1; scanf("%lld%lld",&n,&p); int x,y; int an=ksm(n); int r=gcd(an,p,x,y); int cnt=0; if(p==1){if(n==1) cout<<1; else cout<<"None"; return 0; } if(an%p==0){ cout<<"None"; return 0; } x=(x+p)%p; cout<return 0; }

热门文章