This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub tkmst201/Library
#define PROBLEM "https://yukicoder.me/problems/no/187" #include "Mathematics/garner.hpp" #include <cstdio> #include <vector> int main() { int N; scanf("%d", &N); std::vector<int> b(N), m(N); bool zero = true; for (int i = 0; i < N; ++i) scanf("%d %d", &b[i], &m[i]), zero &= b[i] == 0; constexpr int mod = 1000000007; if (!tk::pre_garner(b, m)) puts("-1"); else if (zero) { long long ans = 1; for (auto c : m) ans = ans * c % mod; printf("%lld\n", ans); } else printf("%d\n", tk::garner<int, long long>(b, m, mod)); }
#line 1 "Test/garner.test.cpp" #define PROBLEM "https://yukicoder.me/problems/no/187" #line 1 "Mathematics/garner.hpp" #include <vector> #include <cassert> #include <type_traits> #line 1 "Mathematics/euclid.hpp" #line 5 "Mathematics/euclid.hpp" #include <utility> #include <tuple> #line 8 "Mathematics/euclid.hpp" #include <cmath> /** * @brief https://tkmst201.github.io/Library/Mathematics/euclid.hpp */ namespace tk { template<typename T> constexpr T gcd(T a, T b) noexcept { static_assert(std::is_integral<T>::value); assert(a >= 0); assert(b >= 0); while (b != 0) { const T t = a % b; a = b; b = t; } return a; } template<typename T> constexpr T lcm(T a, T b) noexcept { static_assert(std::is_integral<T>::value); assert(a >= 0); assert(b >= 0); if (a == 0 || b == 0) return 0; return a / gcd(a, b) * b; } template<typename T> constexpr std::tuple<T, T, T> ext_gcd(T a, T b) noexcept { static_assert(std::is_integral<T>::value); static_assert(std::is_signed<T>::value); assert(a != 0); assert(b != 0); T a1 = (a > 0) * 2 - 1, a2 = 0, b1 = 0, b2 = (b > 0) * 2 - 1; a = std::abs(a); b = std::abs(b); while (b > 0) { const T q = a / b; T tmp = a - q * b; a = b; b = tmp; tmp = a1 - q * b1; a1 = b1; b1 = tmp; tmp = a2 - q * b2; a2 = b2; b2 = tmp; } return {a, a1, a2}; } } // namespace tk #line 1 "Mathematics/mod_pow_inv.hpp" #line 6 "Mathematics/mod_pow_inv.hpp" /** * @brief https://tkmst201.github.io/Library/Mathematics/mod_pow_inv.hpp */ namespace tk { template<typename T> constexpr T mod_pow(T x, T n, T m) noexcept { static_assert(std::is_integral<T>::value); assert(m > 0); assert(n >= 0); x = x % m + (x >= 0 ? 0 : m); T res = 1 % m; while (n > 0) { if (n & 1) res = res * x % m; x = x * x % m; n >>= 1; } return res; } template<typename T> constexpr T mod_inv(T x, T m) noexcept { static_assert(std::is_integral<T>::value); static_assert(std::is_signed<T>::value); assert(m > 0); x = x % m + (x >= 0 ? 0 : m); T x1 = 1, y = m, y1 = 0; while (y > 0) { const T q = x / y; T tmp = x - q * y; x = y; y = tmp; tmp = x1 - q * y1; x1 = y1; y1 = tmp; } assert(x == 1); if (x1 == m) x1 = 0; if (x1 < 0) x1 += m; return x1; } } // namespace tk #line 10 "Mathematics/garner.hpp" /** * @brief https://tkmst201.github.io/Library/Mathematics/garner.hpp */ namespace tk { template<typename T> bool pre_garner(std::vector<T> & b, std::vector<T> & m) noexcept { static_assert(std::is_integral<T>::value); static_assert(std::is_signed<T>::value); for (int i = 0; i < static_cast<int>(b.size()); ++i) { b[i] = b[i] % m[i] + (b[i] >= 0 ? 0 : m[i]); for (int j = 0; j < i; ++j) { T g = gcd(m[i], m[j]); if ((b[i] - b[j]) % g != 0) return false; m[i] /= g; m[j] /= g; T gi = gcd(g, m[i]), gj = g / gi; do { g = gcd(gi, gj); gi *= g; gj /= g; } while (g != 1); m[i] *= gi; m[j] *= gj; b[i] %= m[i]; b[j] %= m[j]; } } return true; } template<typename T, typename U> T garner(const std::vector<T> & b, const std::vector<T> & m, const T M) { static_assert(std::is_integral<T>::value); assert(b.size() == m.size()); const int n = b.size(); assert(n > 0); { T g = 0; for (auto v : m) { assert(v > 0); g = gcd(g, v); } assert(n == 1 || g == 1); } assert(M > 0); std::vector<T> sum(n + 1, 0), ip(n + 1, 1); for (int i = 0; i < n; ++i) { if (m[i] == 1) continue; U t = (b[i] % m[i] + static_cast<U>(2) * m[i] - sum[i]) % m[i] * mod_inv(ip[i], m[i]) % m[i]; for (int j = i + 1; j < n; ++j) { sum[j] = (sum[j] + ip[j] * t) % m[j]; ip[j] = static_cast<U>(ip[j]) * m[i] % m[j]; } sum[n] = (sum[n] + ip[n] * t % M) % M; ip[n] = static_cast<U>(ip[n]) * m[i] % M; } return sum.back(); } } // namespace tk #line 4 "Test/garner.test.cpp" #include <cstdio> #line 7 "Test/garner.test.cpp" int main() { int N; scanf("%d", &N); std::vector<int> b(N), m(N); bool zero = true; for (int i = 0; i < N; ++i) scanf("%d %d", &b[i], &m[i]), zero &= b[i] == 0; constexpr int mod = 1000000007; if (!tk::pre_garner(b, m)) puts("-1"); else if (zero) { long long ans = 1; for (auto c : m) ans = ans * c % mod; printf("%lld\n", ans); } else printf("%d\n", tk::garner<int, long long>(b, m, mod)); }