1370 Biorhythms

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1370

题解:

中国剩余定理

已知

(n+d)%23=a;

(n+d)%28=b;

(n+d)%33=c;

使33×28×a被23除余1,用33×28×6=5544;

使23×33×b被28除余1,用23×33×19=14421;

使23×28×c被33除余1,用23×28×2=1288。

因此有

(5544×p+14421×e+1288×i)% lcm(23,28,33) =n+d

又23、28、33互质,即lcm(23,28,33)= 21252;

所以有n=(5544×p+14421×e+1288×i-d)%21252

本题所求的是最小整数解,避免n为负,因此最后结果为n= [n+21252]% 21252。

代码中a数组代表除数,w数组代表余数。

/*
 * Author: Haipz
 * School: HDU
 * File Name: 1370.cpp
 */
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cctype>
#include <cfloat>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
using namespace std;

int gcd(int a, int b) {
    if (b) return gcd(b, a % b);
    return a;
}

int ex_gcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    int d = ex_gcd(b, a % b, y, x);
    y -= a/b*x;
    return d;
}

int CRT(int a[], int w[], int len) {
    int res = 0, n = 1;
    for (int i = 0; i < len; ++i) n *= w[i];
    for (int i = 0; i < len; ++i) {
        int m = n/w[i], x, y;
        int d = ex_gcd(w[i], m, x, y);
        res = (res + y*m*a[i]) % n;
    }
    return (res % n + n) % n;
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int w[3] = {23, 28, 33}, a[3], d, ics = 0;
        while (scanf("%d%d%d%d", &a[0], &a[1], &a[2], &d), !(a[0] == -1 && a[1] == -1 && a[2] == -1 && d == -1)) {
            int lcm = w[0]*w[1]/gcd(w[0], w[1])*w[2]/gcd(w[0]*w[1]/gcd(w[0], w[1]), w[2]);
            int ans = (CRT(a, w, 3) - d + lcm) % lcm;
            if (ans == 0) ans += lcm;
            printf("Case %d: the next triple peak occurs in %d days.\n", ++ics, ans);
        }
    }
    return 0;
}
转载保留版权:http://haipz.com/blog/i/5543 - 海胖博客