poj1006 Biorhythms ——中国剩余定理入门题

April 17, 2013
POJ

题目链接：http://poj.org/problem?id=1006 题目大意：　　人体有三个周期，23，28，33. 对于每个周期分别给出从第0天开始，这三个周期的高潮出现的一个日期，不一定是第一次，p , e , i 。给出一个天数 d 表示今年已经过去了多少天，计算在这 d 天之后，三个高潮同时出现的那一天距离现在还有多少天。思路：　　23， 28， 33 是两两互素的，题目意思就是求一个数字 x ，使得这个数字 x 和 p 对23同余，同时 x 和 e 对28同余，同时 x 和 i 对33同余。所以可以用中国剩余定理解。这是一个同余方程组。 x = p(mod 23); x = e (mod 28); x = i(mod 33); 这里的’=‘代表同余符号。　　因为求的是大于d的，所以，当求得的解小于等于d的时候，要加上模 23*28*33；直到解大于d为止。


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long int LL;
const int MAXN =  0x3f3f3f3f;
const int  MIN =  -0x3f3f3f3f;
const double eps = 1e-9;
const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
  {1,1},{1,-1},{-1,-1}};
int d, p, e, i, m[4], a[4];
LL M, Mi;
void exgcd(int a, int b, int &d, int &x, int &y){
  if (!b){
    x = 1; y = 0; d = a; return;
  }else{
    exgcd(b, a % b, d, x, y);
    int tem = x; x = y; y = tem - (a / b) * y;
  }
}

int china(int r){
  int ans = 0, d, x0, y0;
  for (int i = 1; i <= r; ++i){
    M *= m[i];
  }
  for (int i = 1; i <= r; ++i){
    Mi = M / m[i]; exgcd(Mi, m[i], d, x0, y0);
    ans = (ans + a[i] * Mi * x0) % M;
  }
  if (ans < 0) ans += M;
  return ans;
}

int main(void){
#ifndef ONLINE_JUDGE
  freopen("poj1006.in", "r", stdin);
#endif
  int t = 1;
  while (~scanf("%d%d%d%d", &p, &e, &i, &d)){
    M = 1;
    if (p+e+i+d==-4) break;
    m[1] = 23; m[2] = 28; m[3] = 33;
    a[1] = p; a[2] = e; a[3] = i;
    int ans = china(3);
    while (ans <= d) ans += M;
    printf("Case %d: the next triple peak occurs in %d days.\n", t,ans-d);
    t++;
  }

  return 0;
}

　　中国剩余定理的模板抄的书上的，写代码的时候，竟然把扩展欧几里德写错了……找了好久才发现

Read more