結果

問題 No.2119 一般化百五減算
ユーザー anqooqieanqooqie
提出日時 2022-11-05 19:12:36
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 4,514 bytes
コンパイル時間 2,410 ms
コンパイル使用メモリ 215,260 KB
実行使用メモリ 13,532 KB
最終ジャッジ日時 2024-07-19 11:05:18
合計ジャッジ時間 5,951 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
10,752 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 1 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 1 ms
5,376 KB
testcase_17 AC 2 ms
5,376 KB
testcase_18 AC 2 ms
5,376 KB
testcase_19 AC 2 ms
5,376 KB
testcase_20 TLE -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 1 "main.cpp"
#include <bits/stdc++.h>
#line 1 "/home/anqooqie/.proconlib/tools/mod.hpp"



#include <type_traits>
#line 1 "/home/anqooqie/.proconlib/tools/quo.hpp"



#line 5 "/home/anqooqie/.proconlib/tools/quo.hpp"

namespace tools {

  template <typename M, typename N>
  constexpr ::std::common_type_t<M, N> quo(const M lhs, const N rhs) {
    if (lhs >= 0) {
      return lhs / rhs;
    } else {
      if (rhs >= 0) {
        return -((-lhs - 1 + rhs) / rhs);
      } else {
        return (-lhs - 1 + -rhs) / -rhs;
      }
    }
  }
}


#line 6 "/home/anqooqie/.proconlib/tools/mod.hpp"

namespace tools {

  template <typename M, typename N>
  constexpr ::std::common_type_t<M, N> mod(const M lhs, const N rhs) {
    if constexpr (::std::is_unsigned_v<M> && ::std::is_unsigned_v<N>) {
      return lhs % rhs;
    } else {
      return lhs - ::tools::quo(lhs, rhs) * rhs;
    }
  }
}


#line 1 "/home/anqooqie/.proconlib/tools/inv_mod.hpp"



#line 1 "/home/anqooqie/.proconlib/tools/extgcd.hpp"



#line 7 "/home/anqooqie/.proconlib/tools/extgcd.hpp"

namespace tools {

  template <typename T>
  ::std::tuple<T, T, T> extgcd(T prev_r, T r) {
    T prev_s(1);
    T prev_t(0);
    T s(0);
    T t(1);
    while (r != 0) {
      const T q = ::tools::quo(prev_r, r);
      ::std::tie(prev_r, r) = ::std::make_pair(r, prev_r - q * r);
      ::std::tie(prev_s, s) = ::std::make_pair(s, prev_s - q * s);
      ::std::tie(prev_t, t) = ::std::make_pair(t, prev_t - q * t);
    }

    if (prev_r < T(0)) prev_r = -prev_r;
    return ::std::make_tuple(prev_s, prev_t, prev_r);
  }
}


#line 7 "/home/anqooqie/.proconlib/tools/inv_mod.hpp"

namespace tools {

  template <typename T1, typename T2>
  constexpr T2 inv_mod(const T1 x, const T2 m) {
    const auto [x0, y0, gcd] = ::tools::extgcd(x, m);
    assert(gcd == 1);
    return ::tools::mod(x0, m);
  }
}


#line 4 "main.cpp"

// Source: https://qiita.com/drken/items/ae02240cd1f8edfc86fd
// License: unknown
// Author: drken

namespace tools {

  template <typename Iterator>
  ::std::optional<long long> garner(const Iterator& begin, const Iterator& end, const long long upper_bound) {
    ::std::vector<long long> b, m;
    for (auto it = begin; it != end; ++it) {
      b.push_back(::tools::mod(it->first, it->second));
      m.push_back(it->second);
    }

    ::std::vector<long long> coeffs(m.size(), 1);
    ::std::vector<long long> constants(m.size(), 0);
    ::std::optional<long long> coeffs_n(1);
    long long constants_n = 0;
    for (::std::size_t k = 0; k < b.size(); ++k) {
      long long t = ::tools::mod((b[k] - constants[k]) * ::tools::inv_mod(coeffs[k], m[k]), m[k]);
      for (::std::size_t i = k + 1; i < m.size(); ++i) {
        (constants[i] += t * coeffs[i]) %= m[i];
        (coeffs[i] *= m[k]) %= m[i];
      }
      if (coeffs_n) {
        if ((constants_n += t * *coeffs_n) > upper_bound) return ::std::nullopt;
        if ((*coeffs_n *= m[k]) > upper_bound) coeffs_n = ::std::nullopt;
      } else {
        if (t > 0) return ::std::nullopt;
      }
    }

    return constants_n;
  }
}

namespace tools {

  template <typename Iterator>
  ::std::optional<long long> extended_garner(const Iterator& begin, const Iterator& end, const long long upper_bound) {
    ::std::vector<::std::pair<long long, long long>> v;
    for (auto it = begin; it != end; ++it) {
      v.emplace_back(::tools::mod(it->first, it->second), it->second);
    }

    for (::std::size_t i = 0; i < v.size(); ++i) {
      for (::std::size_t j = 0; j < i; ++j) {
        long long g = ::std::gcd(v[i].second, v[j].second);

        if ((v[i].first - v[j].first) % g != 0) return ::std::nullopt;

        v[i].second /= g;
        v[j].second /= g;

        long long gi = ::std::gcd(v[i].second, g);
        long long gj = g / gi;

        do {
          g = ::std::gcd(gi, gj);
          gi *= g;
          gj /= g;
        } while (g != 1);

        v[i].second *= gi;
        v[j].second *= gj;

        v[i].first %= v[i].second;
        v[j].first %= v[j].second;
      }
    }

    return ::tools::garner(v.begin(), v.end(), upper_bound);
  }
}

using ll = long long;

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  ll N, M;
  std::cin >> N >> M;
  std::vector<std::pair<ll, ll>> v(M);
  for (auto& [C, B] : v) std::cin >> B >> C;

  if (const auto answer = tools::extended_garner(v.begin(), v.end(), N); answer) {
    std::cout << *answer << '\n';
  } else {
    std::cout << "NaN" << '\n';
  }

  return 0;
}
0