1945302_ac_0ms_56k.c

北大大牛代码 1240道题的原代码 超级权威

# include <stdio.h>

void main()
{
  __int64 a11, a12, a21, a22, b11, b12, b21, b22;
  __int64 T, t11, t12, t21, t22;
  __int64 n;
  
  //scanf("%ld",&T);
  while(scanf("%I64d",&n)==1&&n!=-1)
  {
	  if(n == 0)
	  {
		  printf("0\n");
		  continue;
	  }
	 
	  //n = 2*n - 1;
      a11 = a12 = a21 = b11 =  b22 = 1;
      a22 = b12 = b21 =0;
	  n %= 15000;
	  if(n ==0)
		  n = 15000;
	  while(n!=1)
	  {
		  if(n%2==1)
		  {
			  n--;
			  t11 = a11*b11+a12*b21;
			  t12 = a11*b12+a12*b22;
			  t21 = a21*b11+a22*b21;
			  t22 = a21*b12+a22*b22;
			  b11 = t11%10000; b12 = t12%10000;
			  b21 = t21%10000; b22 = t22%10000;
		  }
		  t11 = a11*a11+a12*a21;
		  t12 = a11*a12+a12*a22;
		  t21 = a21*a11+a22*a21;
		  t22 = a21*a12+a22*a22;
		  a11 = t11%10000; a12 = t12%10000;
		  a21 = t21%10000; a22 = t22%10000;
		  n/=2;
	  }
	  t11 = a11*b11+a12*b21;
	  t12 = a11*b12+a12*b22;
	  t21 = a21*b11+a22*b21;
	  t22 = a21*b12+a22*b22;
	  b11 = t11%10000; b12 = t12%10000;
	  b21 = t21%10000; b22 = t22%10000;
	  printf("%ld\n",b12);
  }
}