Chinese Remainder Theorem

Code

#include <tuple>
#include <vector>
std::tuple<long long, long long, long long> ext_gcd(long long a, long long b) {
  if(b == 0ll) {
    return std::tuple<long long, long long, long long>{ a, 1ll, 0ll };
  }
  else {
    auto [g, q, p] = ext_gcd(b, a%b);
    return std::tuple<long long, long long, long long>{ g, p, q-a/b*p };
  }
  ;
}
std::tuple<long long, long long> chinese_remainder_theorem(std::vector<std::tuple<long long, long long>> const& tms) {
  long long r = 0ll;
  long long M = 1ll;
  for(auto [t, m]: tms) {
    auto [g, p, q] = ext_gcd(M, m);
    if((t-r)%g != 0ll) {
      return std::tuple<long long, long long>{ 0ll, -1ll };
    }
    ;
    long long tmp = (t-r)/g*p%(m/g);
    r = r+M*tmp;
    M = M*(m/g);
  };
  return std::tuple<long long, long long>{ (r%M+M)%M, M };
}