結果

問題 No.2119 一般化百五減算
コンテスト
ユーザー anqooqie
提出日時 2022-11-05 19:12:36
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 4,514 bytes
コンパイル時間 2,364 ms
コンパイル使用メモリ 206,832 KB
最終ジャッジ日時 2025-02-08 18:46:05
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21 TLE * 4
権限があれば一括ダウンロードができます

ソースコード

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