D. Wang's Log

版权声明：转载时请以超链接形式标明文章原始出处和作者信息及本声明
http://billjeff.blogbus.com/logs/8221608.html

还是在POJ做题吧~

这道比较简单，没测试过枚举的方法，直观的想是用中国剩余定理（具体流程一开始也给忘了，常年不用- -）。 不过数据得小心，我一开始考虑挺全面的，想到由剩余定理获得的结果可能会小于0，但是没想到会大于21252的情况，WA了好几次，加上这个条件就AC了。

POJ 1006

// Source code for POJ 1006  by billjeff, sep/11/2007

#include <iostream>
using namespace std ;


#define FORI(n)  for( int i = 0 ; i < n ; ++i )
#define FORJ(n)  for( int j = 0 ; j < n ; ++j )

//#define debug

class Remainder{
private:
  static const int MAX = 100 ;
  int _n ;
  int _a[MAX], _m[MAX] ;
protected:
  int ext_gcd( long a, long b, long &x, long &y ){
    long t = a%b ;
    if ( t == 0 ){
      x = 0 ;
      y = 1 ;
      return b ;
    }
    else {
      int d = ext_gcd( b, t, x, y ) ;
      long temp = x ;
      x = y ;
      y = temp-a/b*y ;     
      return d ;
    }
  }
public:
  Remainder( int n = 3 ) : _n(n) {
  }

  void readData(int *a, int *m){
    //cout << "Enter the number of equations: " ;
    //cin >> _n ;
    //cout << "Enter the data of each equation!\n" ;
    FORI(_n)   {
      _a[i] = a[i] ;
      _m[i] = m[i] ;
    }
  }

  long getRemainder(){
    long ri, bi, c1, c2 ;
    long result = 0 ;
    FORI(_n){
      ri = 1 ;
      FORJ(_n)  if ( i != j )   ri *= _m[j] ;
      ext_gcd( ri, _m[i], c1, c2 ) ;
      bi = ri*c1 ;
      result += bi*_a[i] ;
    }
    return result ;
  }
} ;


int main( void ){
  int p, e, i, d ;
  long c = 1 ;
  int m[3] = { 23, 28, 33 } ;
  int a[3] ;
  Remainder r ;
  while ( cin >> p >> e >> i >> d ){
    if ( p+e+i+d == -4 )  break ;
    cout << "Case " << c++ << ": the next triple peak occurs in " ;
    long t = i ;
    if ( p == e && p == i ){
      int temp = d/21252 ;
      cout << 21252*(temp+1)-d ;
    }
    else {
      a[0] = p%23 ; a[1] = e%28 ; a[2] = i%33 ;
      r.readData(a, m) ;
      t = r.getRemainder() ;
#ifdef debug
      cout << "r = " << t << endl ;
#endif
      while ( t < 0 )  t += 21252 ;
      while ( t > 21252 ) t -= 21252 ;
      if ( t <= d )
    cout << t-d+21252 ;
      else
    cout << t-d ;
    }
    cout << " days." << endl ;
  }
  return 0 ;
}