大神的世界

直接說結論 

x mod pi = ki

x =  sigma ni * mi * ki

ni : p1*p2*... / pi

mi : ni 在 mod pi 下的反元素

mi 的可透過 ni 與 pi 做輾轉相除法得到

ex:   ni = 1213   ,     pi = 23

1213 - 52 * 23 = 17

23 - 17 = 6

17 - 2*6 = 5

6 - 5 = 1

回推

=>  -17 + ( -1*(-2) + 1) * 6 = 1    => -17 + 3*6 = 1

=> 3*23 + ( 3*(-1) + (-1) )*17  = 1  =>  3*23 + (-4)*17 =  1

=> -4*1213 + ( -4*(-52) + 3 )*23 = 1  => -4*2013 + 211*23 = 1

所以 mi = -4

另外仔細觀察係數可發現

第 1 項的係數來自前面第 2 項的係數 

第 2 項的係數來自前面第 2 項的係數 * 代入的第 2 項係數 + 前面第 1 項係數

因此，將係數分別用 a b 表示

則 a := b  ,   b = b*代入的第 2 項係數 + a

因為是回推

所以將代入的第 2 項係數存在 stack

總而言之就是這樣

最後記得判別計算出來的數有沒有大於 pi

#include <iostream>
#include <stdint.h>
#include <stack>

using namespace std;

int main()
{
    int32_t p[3];
    int32_t k[3];

    int32_t i;

    while(cin >> p[0]){
        for(i = 1; i<3; i++)
            cin >> p[i];

        for(i = 0; i<3; i++)
            cin >> k[i];

        const int32_t N = p[0] * p[1] * p[2];
        int32_t n[3];

        for(i = 0; i<3; i++)
            n[i] = N/p[i];

        int32_t anti[3];
        for(i = 0; i<3; i++)
        {
            int32_t tmpP, tmpN;
            stack<int32_t> coef;

            tmpP = p[i];
            tmpN = n[i];

            while(tmpN != 1 && tmpP != 1)
                if(tmpN > tmpP){
                    coef.push(-tmpN/tmpP);
                    tmpN %= tmpP;
                }
                else{
                    coef.push(-tmpP/tmpN);
                    tmpP %= tmpN;
                }

            int32_t a, b, tmp;
            a = 1;
            b = coef.top();
            coef.pop();

            while(!coef.empty()){
                tmp = a;
                a = b;
                b = b*coef.top() + tmp;
                coef.pop();
            }
            if(n[i] > p[i])
                anti[i] = a;
            else
                anti[i] = b;
        }

        int32_t money = ( n[0]*anti[0]*k[0] + n[1]*anti[1]*k[1] + n[2]*anti[2]*k[2] ) % N;

        while(money < p[0] || money < p[1] || money < p[2])
            money = money + N;

        cout << money << endl;

    }

    return 0;
}