hdu1005.cpp

杭电ACM1001～1005解体报告

//*************************************************************************
//*程 序 名：HDu1005.CPP                                                  *
//*作    者：FLYLIKEABIRD（LIANG YI MING)                                 *
//*编制时间：2008.09.22                                                   *
//*主要功能: Number Sequence(难）                                         * 
//************************************************************************* 
#include<iostream>
using namespace std;
int main()
{
      int fun(int , int , int) ;
      int a , b ;
      int n ;      
      int k ;
      cin >> a >> b >> n ;
      while(a != 0 && b !=0 && n > 0)
      {
              if(n < 3)
              {
                    k = 1 ;
              }
              else
              {
                    k = fun(a , b , n) ;
              }
              cout << k << endl ;
              cin >> a >> b >> n ;
      }
      return 0;
}


int fun(int aa , int bb , int nn) 
{
      int f[3] ;
      int i ;
      int kk ;
      f[0] = f[1] = f[2] = 1 ;
      for(i = 3 ; i <= nn % 21 ; i ++)    //注意这一句!
      {
              f[i % 3]=(aa * f[(i - 1) % 3] + bb * f[(i - 2) % 3]) % 7 ;
      }
      kk = f[(i - 1) % 3] ;
      return kk ;
}//f[n] 是f[n-1],f[n-2]对7的求余.所以f[n]的结果只有7种0-6.可是f[n-1],f[n-2]的组合有49种.而且当f[n] = f[0],f[n+1] = f[1]的时候,f[n+2] 就等于 f[2].所以周期为n;   找周期的时候你就用
 //for(int i = 2;i < 49;i++) 
 //{f = (A*f[i-2] %7 + B*f[i-1]%7)%7;
 //if(f = f[1] && f[i-1] = f[0]) break;
 //}
 // 那么就找到周期为i-1;