<style>
html, body, .ui-content {
background-image: url(https://truth.bahamut.com.tw/s01/201508/7f0e4bd0e01135c9df434733e0d1544a.JPG);
background-color: #333;
color: #DDD;
}
</style>

###### tags: `Meowmeow Online Judge`

# Problem D. Candies

## Description
Kumari knows that if she divides those candies into groups of size $k_i$, there are $r_i$ candies that will be left. Give you 3 pairs of $k_i$ and $r_i$. Can you calculate at least how many candies Kumari owns?
## Input
The first line has an integer $n$ which indicates how many testcases.
Each testcase contains three lines. The $i$-th line has two integers $k_i$, $r_i$.
• $1 ≤ n ≤ 200,000$
• $1 < r_i < k_i ≤ 10,000$
• gcd($k_i$, $k_j$) = 1 if $i\neq j$

## Output
Please print at least how many candies Kumari owns. It is ensured that the answer can be stored in a
32-bit signed integer.

## 解題思路
中國剩餘定理，有興趣可以去搜尋看看
要注意取餘數時分母要改成乘以乘法反元素

### 時間複雜度
取反元素 $O(lg\ n)$
總時間複雜度 $O(n\ lg\ n)$

## Code

#include <iostream>
#include <vector>
#include <utility>

std::pair<long long int, long long int> extgcd(long long int a, long long int b) {
    if (b == 0) return {1, 0};
    auto [xp, yp] = extgcd(b, a % b);
    return {yp, xp - a / b * yp};
}

int main() {
    int testcase;
    std::cin >> testcase;
    while (testcase--) {
        std::vector< std::pair<int, int> > divider(3);
        long long int product = 1;
        for (int i = 0; i < 3; i++) {
            std::cin >> divider[i].first >> divider[i].second;
            product *= divider[i].first;
        }
        long long int answer = 0;
        for (int i = 0; i < 3; i++) {
            long long int partial = product / divider[i].first;
            answer += (1LL * divider[i].second * extgcd(partial, divider[i].first).first * partial); 
        }
        std::cout << (answer % product + product) % product << std::endl;
    }
    return 0;
}