test/yukicoder/186/main.test.cpp

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Problem: https://yukicoder.me/problems/447
• Link: View error logs on GitHub Actions

Depends on

• Chinese remainder theorem (Mylib/Number/chinese_remainder_algorithm.cpp)
• Extended Euclidean algorithm (Mylib/Number/extended_gcd.cpp)

Code

#define PROBLEM "https://yukicoder.me/problems/447"

#include <iostream>
#include "Mylib/Number/chinese_remainder_algorithm.cpp"

namespace hl = haar_lib;

int main() {
  int64_t x1, y1, x2, y2, x3, y3;
  std::cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;

  if (auto res = hl::chinese_remainder_algorithm({x1, x2, x3}, {y1, y2, y3}); res) {
    const auto [r, m] = *res;
    std::cout << (r == 0 ? m : r) << std::endl;
  } else {
    std::cout << -1 << std::endl;
  }

  return 0;
}

#line 1 "test/yukicoder/186/main.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/447"

#include <iostream>
#line 2 "Mylib/Number/chinese_remainder_algorithm.cpp"
#include <cassert>
#include <optional>
#include <vector>
#line 2 "Mylib/Number/extended_gcd.cpp"
#include <tuple>

namespace haar_lib {
  auto ext_gcd(int64_t a, int64_t b) -> std::tuple<
      int64_t,  // gcd
      int64_t,  // p
      int64_t   // q
      > {
    if (b == 0) return std::make_tuple(a, 1, 0);
    const auto [d, q, p] = ext_gcd(b, (a + b) % b);
    return std::make_tuple(d, p, q - a / b * p);
  }
}  // namespace haar_lib
#line 6 "Mylib/Number/chinese_remainder_algorithm.cpp"

namespace haar_lib {
  std::optional<std::pair<int64_t, int64_t>> chinese_remainder_algorithm(
      int64_t b1, int64_t m1,
      int64_t b2, int64_t m2) {
    const auto [d, p, q] = ext_gcd(m1, m2);
    if ((b2 - b1) % d != 0) return std::nullopt;
    const int64_t m = m1 * m2 / d;
    const int64_t t = ((b2 - b1) * p / d) % (m2 / d);
    const int64_t r = (b1 + m1 * t + m) % m;
    return {{r, m}};
  }

  std::optional<std::pair<int64_t, int64_t>> chinese_remainder_algorithm(
      const std::vector<int64_t> &bs,
      const std::vector<int64_t> &ms) {
    assert(bs.size() == ms.size());
    int64_t R = 0, M = 1;
    for (int i = 0; i < (int) bs.size(); ++i) {
      const auto res = chinese_remainder_algorithm(R, M, bs[i], ms[i]);
      if (not res) return std::nullopt;
      const auto [r, m] = *res;
      R                 = r;
      M                 = m;
    }
    return {{R, M}};
  }
}  // namespace haar_lib
#line 5 "test/yukicoder/186/main.test.cpp"

namespace hl = haar_lib;

int main() {
  int64_t x1, y1, x2, y2, x3, y3;
  std::cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;

  if (auto res = hl::chinese_remainder_algorithm({x1, x2, x3}, {y1, y2, y3}); res) {
    const auto [r, m] = *res;
    std::cout << (r == 0 ? m : r) << std::endl;
  } else {
    std::cout << -1 << std::endl;
  }

  return 0;
}

Back to top page