結果

問題 No.195 フィボナッチ数列の理解(2)
ユーザー risujirohrisujiroh
提出日時 2019-03-17 10:25:08
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 684 ms / 5,000 ms
コード長 5,088 bytes
コンパイル時間 1,961 ms
コンパイル使用メモリ 181,656 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-20 10:34:18
合計ジャッジ時間 6,941 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 102 ms
4,380 KB
testcase_01 AC 684 ms
4,376 KB
testcase_02 AC 105 ms
4,376 KB
testcase_03 AC 104 ms
4,376 KB
testcase_04 AC 103 ms
4,376 KB
testcase_05 AC 101 ms
4,376 KB
testcase_06 AC 103 ms
4,380 KB
testcase_07 AC 161 ms
4,376 KB
testcase_08 AC 178 ms
4,380 KB
testcase_09 AC 106 ms
4,376 KB
testcase_10 AC 108 ms
4,376 KB
testcase_11 AC 107 ms
4,376 KB
testcase_12 AC 103 ms
4,380 KB
testcase_13 AC 107 ms
4,380 KB
testcase_14 AC 106 ms
4,376 KB
testcase_15 AC 106 ms
4,380 KB
testcase_16 AC 107 ms
4,380 KB
testcase_17 AC 108 ms
4,380 KB
testcase_18 AC 108 ms
4,380 KB
testcase_19 AC 108 ms
4,376 KB
testcase_20 AC 108 ms
4,380 KB
testcase_21 AC 108 ms
4,380 KB
testcase_22 AC 107 ms
4,380 KB
testcase_23 AC 107 ms
4,376 KB
testcase_24 AC 108 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;

template<unsigned P> struct ModInt {
  using M = ModInt;
  unsigned v;
  ModInt() : v(0) {}
  template<class Z> ModInt(Z x) : v(x >= 0 ? x % P : -x % P ? P - -x % P : 0) {}
  constexpr ModInt(unsigned v, int) : v(v) {}
  static constexpr unsigned p() { return P; }
  M operator+() const { return *this; }
  M operator-() const { return {v ? P - v : 0, 0}; }
  explicit operator bool() const noexcept { return v; }
  bool operator!() const noexcept { return !(bool) *this; }
  M operator*(M r) const { return M(*this) *= r; }
  M operator/(M r) const { return M(*this) /= r; }
  M operator+(M r) const { return M(*this) += r; }
  M operator-(M r) const { return M(*this) -= r; }
  bool operator==(M r) const { return v == r.v; }
  bool operator!=(M r) const { return !(*this == r); }
  M& operator*=(M r) { v = (uint64_t) v * r.v % P; return *this; }
  M& operator/=(M r) { return *this *= r.inv(); }
  M& operator+=(M r) { v = r.v < P - v ? v + r.v : v - (P - r.v); return *this; }
  M& operator-=(M r) { v = r.v <= v ? v - r.v : v + (P - r.v); return *this; }
  M inv() const {
    int a = v, b = P, x = 1, u = 0;
    while (b) {
      int q = a / b;
      swap(a -= q * b, b);
      swap(x -= q * u, u);
    }
    assert(a == 1);
    return x;
  }
  template<class Z> M pow(Z n) const {
    n = n >= 0 ? n % (P - 1) : P - 1 - -n % (P - 1);
    M res = 1;
    for (M a = *this; n; a *= a, n >>= 1) if (n & 1) res *= a;
    return res;
  }
  template<class Z> friend M operator*(Z l, M r) { return M(l) *= r; }
  template<class Z> friend M operator/(Z l, M r) { return M(l) /= r; }
  template<class Z> friend M operator+(Z l, M r) { return M(l) += r; }
  template<class Z> friend M operator-(Z l, M r) { return M(l) -= r; }
  friend ostream& operator<<(ostream& os, M r) { return os << r.v; }
  friend istream& operator>>(istream& is, M& r) { lint x; is >> x; r = x; return is; }
  template<class Z> friend bool operator==(Z l, M r) { return M(l) == r; }
  template<class Z> friend bool operator!=(Z l, M r) { return !(l == r); }
};
using Mint = ModInt<(unsigned) 1e9 + 7>;

template<class T> pair<int, T> gauss_jordan(VV<T>& A) {
  int n = A.size(), m = A[0].size(), r = 0;
  T det = 1;
  for (int j = 0; j < m; ++j) {
    for (int i = r + 1; i < n; ++i) if (A[i][j]) {
      swap(A[r], A[i]);
      det = -det;
      break;
    }
    if (!A[r][j]) continue;
    // if (abs(A[r][j]) < 1e-12) continue;
    det *= A[r][j];
    auto inv = (T) 1 / A[r][j];
    for (auto&& e : A[r]) e *= inv;
    for (int i = 0; i < n; ++i) if (i != r and A[i][j]) {
      auto c = A[i][j];
      for (int k = 0; k < m; ++k) {
        A[i][k] -= c * A[r][k];
      }
    }
    if (++r == n) break;
  }
  return {r, det * (r == n)};
}

template<class Z> Z ext_gcd(Z a, Z b, Z& x, Z& y) {
  Z u = y = 0, v = x = 1; 
  while (b) {
    Z q = a / b;
    swap(a -= q * b, b);
    swap(x -= q * u, u);
    swap(y -= q * v, v);
  }
  return a;
}
template<class Z> pair<Z, Z> bezout(Z a, Z b, Z c) {
  Z x, y, d = ext_gcd(a, b, x, y);
  if (c % d) return {0, 0};
  Z q = c / (a + b) / b;
  Z r = c / d % b * x % b;
  Z mn = numeric_limits<Z>::max();
  for (int i = -1; i <= 1; ++i) {
    Z nx = (q + i) * b + r;
    Z ny = (c - a * nx) / b;
    if (abs(ny - nx) < mn) {
      mn = abs(ny - nx);
      x = nx, y = ny;
    }
  }
  return {x, y};
}

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  constexpr int N = 44;
  int X, Y, Z; cin >> X >> Y >> Z;
  V<> F{1, 0};
  for (int i = 2; i <= N; ++i) {
    F.push_back(F[i - 1] + F[i - 2]);
  }
  pair<int, int> res{2e9, 2e9};
  for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) for (int k = 0; k < N; ++k) {
    VV<Mint> A{{F[i], F[i + 1]}, {F[j], F[j + 1]}, {F[k], F[k + 1]}};
    auto B = A;
    B[0].push_back(X);
    B[1].push_back(Y);
    B[2].push_back(Z);
    if (i == 3 and j == 19 and k == 16) {
      // cerr << "A(" << A.size() << ", " << A[0].size() << ")\n"; for (const auto& v : A) { for (const auto& e : v) cerr << e << '\t'; cerr << '\n'; }
      // cerr << "B(" << B.size() << ", " << B[0].size() << ")\n"; for (const auto& v : B) { for (const auto& e : v) cerr << e << '\t'; cerr << '\n'; }
      // cerr << rA << ' ' << rB << '\n';
    }
    int rA = gauss_jordan(A).first;
    int rB = gauss_jordan(B).first;
    if (rA != rB) continue;
    int x, y;
    if (rA == 1) {
      if (!F[i]) x = 1, y = X / F[i + 1];
      else if (!F[i + 1]) x = X / F[i], y = 1;
      else {
        tie(x, y) = bezout(F[i], F[i + 1], X);
        if (x <= 0 or y <= 0) continue;
        while (x - F[i + 1] > 0) {
          x -= F[i + 1];
          y += F[i];
        }
      }
    } else {
      x = B[0][2].v, y = B[1][2].v;
      if (x <= 0 or y <= 0) continue;
      if (F[i] * x + F[i + 1] * y != X) continue;
    }
    if (make_pair(x, y) < res) {
      res = {x, y};
    }
  }
  if (res.first > 1e9) cout << -1 << '\n';
  else cout << res.first << ' ' << res.second << '\n';
}
0