杭州acm 1005题,为什么总是Time Limit Exceeded?求解
发布网友
发布时间:2023-08-13 02:44
我来回答
共1个回答
热心网友
时间:2023-08-25 03:59
楼主请把原题一起发上来,这个看着晕,对7求余不晓得是什么意思
#include<stdio.h>
int b[2][2];
int A,B;
void f(int n);
int main()
{
int n;
while(scanf("%d%d%d",&A,&B,&n)&&(A||B||n))
{
if(n==1||n==2)
{
printf("1\n");
continue;
}
A%=7;
B%=7;
b[0][0]=A;
b[0][1]=B;
b[1][0]=1;
b[1][1]=0;
f(n-2);
printf("%d\n",(b[0][0]+b[0][1])%7);
}
return 0;
}
void f(int n)
{
int b00,b01,b10,b11,c00,c01,c11,c10;
if(n==0)
{
b[0][0]=1;
b[1][0]=b[0][1]=0;
b[1][1]=1;
return;
}
if(n==1)
{
b[0][0]=A;
b[0][1]=B;
b[1][0]=1;
b[1][1]=0;
return;
}
if(n%2==0)
{
n/=2;
f(n);
b00=b[0][0]*b[0][0]+b[0][1]*b[1][0];
b01=b[0][0]*b[0][1]+b[0][1]*b[1][1];
b10=b[1][0]*b[0][0]+b[1][1]*b[1][0];
b11=b[1][0]*b[0][1]+b[1][1]*b[1][1];
b[0][0]=b00%7;
b[0][1]=b01%7;
b[1][0]=b10%7;
b[1][1]=b11%7;
}
else
{
n/=2;
f(n);
b00=b[0][0]*b[0][0]+b[0][1]*b[1][0];
b01=b[0][0]*b[0][1]+b[0][1]*b[1][1];
b10=b[1][0]*b[0][0]+b[1][1]*b[1][0];
b11=b[1][0]*b[0][1]+b[1][1]*b[1][1];
c00=b00*A+b01;
c01=b00*B;
c10=b10*A+b11;
c11=b10*B;
b[0][0]=c00%7;
b[0][1]=c01%7;
b[1][0]=c10%7;
b[1][1]=c11%7;
}
}