[UVA] UVa 756 - Biorhythms

題目連結

題意

給你四個數字 r1 , r2 , r3 ,d;

x ≡ r1 ( mod 23 )

x ≡ r2 ( mod 28 )

x ≡ r3 ( mod 33 )

求出x後，

如果 x > d ，輸出 x - d

如果 x < d ，輸出 x + 21252 - d

--------------------------------------------------

我的作法

這裡有一個小知識喔!

13 ≡ 2 (mod 11)

不是說 13 % 11 等於2喔!

是說 13 % 11 == 2 %11的意思，稱作 13 和 2 同餘，

所以也可以寫成像這樣

13 ≡ 35 (mod 11)

因為 13 % 11 == 35 % 11 == 2，

所以，

當題目給你的 r1 >23 時， 例如 r1 = 25 ，

你可以先把他變成 r1 % 23 = 25 % 23 = 2

因為 x ≡ 25 (mod 23) 就是 x ≡ 2 (mod 23)。

*****

這種類型的題目就是將柿子展開!
一層一層求解，
這是我們老師提供給我們看的解法，可以參考

下面有我把這題的柿子展開的方程式!

--------------------------------------------------

/* 20151020
 * hanting
 * UVa 756 - Biorhythms
 * C++
 */
#include <iostream>
using namespace std;
/* 已知 r1 ,r2 ,r3
 *  x = 23 * p1 + r1 ,r1 < 23
 *  x = 23 * (28 * p2 + R2) + r1 ,R2 < 28
 *     = 23 * 28 * p2 + [ (23 * R2) + r1 ]
 *     => r2 = [ (23 * R2) + r1 ] % 28
 *  x = 23 * 28 * p2 + [ (23 * R2) + r1 ]
 *     = 23 * 28 * (33 * p3 + R3) + [ (23 * R2) + r1 ] ,R3 < 33
 *     = 23 * 28 * 33 * p3 + { (23 * 28 * R3) +  [ (23 * R2) + r1 ] }
 *     => r3 = { (23 * 28 * R3) +  [ (23 * R2) + r1 ] } % 33
 */
inline int solve(int r1 , int r2 , int r3)
{
    int x;
    int R2 = 0 , R3 = 0;
    for(; R2 < 28 ; R2++)
    {
        if(r2 == (23 * R2 + r1) % 28) break;
    }
    for(; R3 < 33 ; R3++)
    {
        if(r3 == ((23 * 28 * R3) + ((23 * R2) + r1)) % 33) break;
    }
    int k = ( (23 * 28 * R3 ) +  ( (23 * R2) + r1 ) );
    for(int p3 = 1 ; ; p3--)
    {
        int tmp = 23 * 28 * 33 * p3 + k;
        if(tmp <= 0 ) break;
        x = tmp;
    }
    return x;
}
int main()
{
    int phy , emo , intel, today;
    int case_num = 1;
    while(cin >> phy >> emo >> intel >> today and phy != -1)
    {
        int x = solve( phy%23 , emo%28 , intel%33 );
        int ans = ((x + 21252) - today) % 21252;
        cout << "Case " << case_num++ << ": the next triple peak occurs in " << (!ans ? 21252 : ans )   << " days." << endl;
    }
    return 0;
}