POJ 1006 Biorhythms ( CRT, ExtGCD )

1006 -- Biorhythms

題意：
細節不好說明，但總之給 p, i, e, d，滿足聯立模方程式：
( x + d ) % 23 = p
( x + d ) % 28 = e
( x + d ) % 33 = i
求 x。

解法：
就是一個中國剩餘定理模板。28 非質數，如果要用尤拉定理搞要先求 phi 函數才能求模逆元，但最近終於搞懂 ext_gcd，輕鬆一波。

#include <bits/stdc++.h>
using namespace std;

int int_pow( int v, int p, int m ){
  int res = not ( v == 0 and p );
  while( p ){
    if( p & 1 ) res = 1LL * res * v % m;
    p >>= 1;
    v = 1LL * v * v % m;
  }
  return res;
}

void ext_gcd( int a, int &x, int b, int &y ){
  if( b == 0 ){
    x = 1;
    y = 0;
    return;
  }
  int xx, yy;
  ext_gcd( b, xx, a % b, yy );
  x = yy;
  y = xx - a / b * yy;
}

int mod_inv( int a, int m ){
  int x, y;
  ext_gcd( a, x, m, y );
  return x;
}

int crt( const vector< int > &a, const vector< int > &m ){
  int M = 1;
  for( int i = 0; i < m.size(); ++i ){
    M *= m[ i ];
  }
  int res = 0;
  for( int i = 0; i < a.size(); ++i ){
    int Mi = M / m[ i ];
    int rMi = mod_inv( Mi, m[ i ] );
    ( res += 1LL * Mi * rMi % M * a[ i ] % M ) %= M;
  }
  if( res < 0 ) res += M;
  return res;
}

signed main(){
  ios::sync_with_stdio( 0 );
  int p, e, i, d;
  for( int kase = 1; cin >> p >> i >> e >> d and p != -1; ++kase ){
    vector< int > a = { p, i, e };
    vector< int > m = { 23, 28, 33 };
    int xpd = crt( a, m );
    int x = xpd - d;
    if( x <= 0 ) x += 23 * 28 * 33;
    cout << "Case " << kase << ": the next triple peak occurs in " << x << " days.\n";
  }
  return 0;
}