1847644_ac_93ms_24k.c

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

# include <stdio.h>

void main()
{
  int a11, a12, a21, a22, b11, b12, b21, b22;
  long i, n, t11, t12, t21, t22;
  

  while(scanf("%ld",&n)==1&&n!=-1)
  {
   if(!n) {printf("0\n");continue;}
   if(n==1) {printf("1\n");continue;}
     a11 = a12 = a21 = b11 = b12 = b21 = 1;
     a22 = b22 = 0;
     while(n > 15000)
       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%10000; t12 = t12%10000;
      t21 = t21%10000; t22 = t22%10000;
      a11 = t11;a12 = t12;a21 = t21;a22= t22;
     }
    printf("%d\n",a12);
  }
}