f070. 1. 韓信點兵 (HanXin) -- 2020年5月TOI練習賽新手組 | From: [203.72.178.1] | 發表日期 : 2024-10-01 17:45

#include <iostream>

using namespace std;

 

int ModuloInverse(int number, int MOD) {

bool flag = false;

int left1 = 1, left2 = 0, right1 = 0, right2 = 1, temporary, mod = MOD;

while (number % mod) {

if (!flag) {

left1 -= number / mod * right1;

left2 -= number / mod * right2;

}

else {

right1 -= number / mod * left1;

right2 -= number / mod * left2;

}

flag = !flag, temporary = number, number = mod, mod = temporary % mod;

}

return flag ? (left1 % MOD + MOD) % MOD : (right1 % MOD + MOD) % MOD;

}

 

int mods[3], remains[3];

 

int ChineseRemainderTheorem() {

long long mod = mods[0], result = remains[0], buffer;

for (int i = 1; i < 3; ++i) {

buffer = mod * mods[i];

result = (result * ModuloInverse(mods[i], mod) * mods[i] + remains[i] * ModuloInverse(mod, mods[i]) * mod) % buffer;

mod = buffer;

}

return result;

}

 

int main() {

cin.sync_with_stdio(false), cin.tie(nullptr);

for (int i = 0; i < 3; ++i)

cin >> mods[i] >> remains[i];

cout << ChineseRemainderTheorem() << '\n';

}