为什么 kk的值改变？？输入3 6（在快速幂那里）

#include #include #include #include #define ll long long
#define mod 100000000

using namespace std;

ll n,m;

struct ju{ll m[3][3];}ans,base;

ju mul(ju a,ju b){

CPP

ju res;
memset(res.m,0,sizeof(res.m));
for(int i=1;i<=3;i++)
   for(int j=1;j<=3;j++)
       if(a.m[i][j]){
   	     for(int k=1;k<=3;k++)res.m[i][k]+=(a.m[i][j]%mod)*(b.m[j][k]%mod)%mod;
       }
return res;

}

ll gcd(ll a,ll b){

CPP

if(!b)return a;
else return gcd(b,a%b);

}

void poww(ll kk){

CPP

while(kk){
	if(kk&1)ans=mul(ans,base);		
	base=mul(base,base);
	kk>>=1;
}

}

int main(){

// freopen("in.txt","r",stdin);

scanf("%lld%lld",&n,&m);

ll gc=gcd(n,m);

if(gc<=2){printf("1");return 0;}

base.m[1][1]=base.m[1][2]=base.m[2][1]=1;

ans.m[1][1]=ans.m[1][2]=1;

poww(gc-2);

printf("%lld",ans.m[1][1]%mod);

return 0;

}

为什么 kk的值改变？？输入3 6（在快速幂那里）

讨论操作

回复

相关推荐

为什么 kk的值改变？？输入3 6（在快速幂那里）