本地又跟洛谷IDE出现差异
查看原帖
本地又跟洛谷IDE出现差异
239832
sipu6174楼主2020/8/27 10:07

是哪里的ub?

#include <bits/stdc++.h>
using namespace std;
const int mod=1e8;
int n,m,g;
long long tmp[3],f[3];
struct mat{
   long long a[3][3];
   mat(){a[1][1]=a[2][2]=1;}
}Tmp;
void print(mat x){
   for(int i=1;i<=2;i++){
      for(int j=1;j<=2;j++)
         cout<<x.a[i][j]<<" ";
      puts("");
   }
}
void mul(long long* a,mat b){
   tmp[1]=tmp[2]=0;
   for(int i=1;i<=2;i++)
      for(int j=1;j<=2;j++)
         tmp[i]=(tmp[i]+a[j]*b.a[i][j])%mod;
   memcpy(a,tmp,sizeof tmp);
}
mat mul(mat a,mat b){
   memset(Tmp.a,0,sizeof Tmp.a);
   for(int i=1;i<=2;i++)
      for(int j=1;j<=2;j++)
         for(int k=1;k<=2;k++)
            Tmp.a[i][j]=1ll*(Tmp.a[i][j]+a.a[i][k]*b.a[k][j])%mod;
   return Tmp;
}
mat qpow(mat a,int n){
   mat e;
   while(n){
      if(n&1) e=mul(e,a);
      a=mul(a,a);
      n>>=1;
   }
   return e;
}
int main(){
   cin>>n>>m;
   g=__gcd(n,m);
   mat t;
   t.a[1][1]=0;t.a[1][2]=t.a[2][1]=t.a[2][2]=1;
   t=qpow(t,g);
   f[1]=0,f[2]=1;
   mul(f,t);
   cout<<f[1];
   return 0;
}

输入:2020 972020

本地输出:6765

IDE:69090989

2020/8/27 10:07
加载中...