2011-12-18 03:16:34

地址：

题意：求公式的第n项。f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.

mark：矩阵乘法，快速幂。

代码：

# include 
     
       # define REP(i,a) for(i = 0 ;i < a ; i++) void mul(int a[2][2], int b[2][2]) {
   int i, j, c[2][2] ;     c[0][0] = (a[0][0]*b[0][0] + a[0][1]*b[1][0]) % 7 ;     c[0][1] = (a[0][0]*b[0][1] + a[0][1]*b[1][1]) % 7 ;     c[1][0] = (a[1][0]*b[0][0] + a[1][1]*b[1][0]) % 7 ;     c[1][1] = (a[1][0]*b[0][1] + a[1][1]*b[1][1]) % 7 ;     REP(i,2) REP(j,2) a[i][j] = c[i][j] ; } void qpow(int m[2][2], int n) {
   int rst[2][2] = {
   1,0,0,1} ; int buff[2][2] ; int i, j ;     REP(i,2)REP(j,2) buff[i][j] = m[i][j] ; while (n)     {
   if (n&1) mul(rst, buff) ;         mul(buff, buff) ;         n >>= 1 ;     }     REP(i,2) REP(j,2) m[i][j] = rst[i][j] ; } int main () {
   int a, b, n ; int m[2][2] ; while (~scanf ("%d%d%d", &a, &b, &n) && (a||b||n))     {
   if (n <= 2){puts ("1") ; continue ;}         m[0][0] = 0, m[0][1] = b%7,         m[1][0] = 1, m[1][1] = a%7 ;         qpow(m,n-2) ;         printf ("%d\n", (m[0][1] + m[1][1]) % 7) ;     } return 0 ; }