1945280_tle.c

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

# include <stdio.h>

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