結果

問題 No.1794 Continued Fraction
コンテスト
ユーザー Kiogoll
提出日時 2022-02-13 11:37:35
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 10 ms / 2,000 ms
コード長 5,190 bytes
コンパイル時間 1,714 ms
コンパイル使用メモリ 179,952 KB
実行使用メモリ 26,808 KB
最終ジャッジ日時 2024-06-29 05:30:44
合計ジャッジ時間 3,319 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'std::string smax(std::string, std::string)':
main.cpp:121:1: warning: control reaches end of non-void function [-Wreturn-type]
  121 | }
      | ^
main.cpp: In function 'std::string smin(std::string, std::string)':
main.cpp:139:1: warning: control reaches end of non-void function [-Wreturn-type]
  139 | }
      | ^

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ull = unsigned long long;
const ll _mod = 998244353;
const ll _MOD = 1000000007;
const ll INF = 1ll << 60;
const ll inf = -(1ll << 60);
const double PI = 3.141592653589793;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
struct union_find {
  vector<ll> p, s;
  union_find(ll n) : p(n, -1), s(n, 1) {}
  ll root(ll x) {
    if (p[x] == -1) return x;
    else return p[x] = root(p[x]);
  }
  bool same(ll x, ll y) { return root(x) == root(y); }
  ll unite(ll x, ll y) {
    x = root(x); y = root(y);
    if (x == y) return false;
    if (s[x] < s[y]) swap(x, y);
    p[y] = x;
    s[x] += s[y];
    return true;
  }
  ll size(ll x) { return s[root(x)]; }
};
struct BIT {
public:
  ll n;
  vector<ll> a;
  BIT(ll n) :n(n), a(n + 1, 0) {}
  void add(ll i, ll x) {
    i++;
    if (i == 0) return;
    for (ll k = i; k <= n; k += (k & -k)) {
      a[k] += x;
    }
  }
  ll sum(ll i, ll j) {
    return sum_sub(j) - sum_sub(i - 1);
  }
  ll sum_sub(ll i) {
    i++;
    ll s = 0;
    if (i == 0) return s;
    for (ll k = i; k > 0; k -= (k & -k)) {
      s += a[k];
    }
    return s;
  }
  ll lower_bound(ll x) {
    if (x <= 0) {
      return 0;
    }
    else {
      ll i = 0; ll r = 1;
      while (r < n) r = r << 1;
      for (int len = r; len > 0; len = len >> 1) {
        if (i + len < n && a[i + len] < x) {
          x -= a[i + len];
          i += len;
        }
      }
      return i;
    }
  }
};
struct segment_tree {
private:
  ll n;
  vector<ll> node;
public:
  segment_tree(vector<ll> v) {
    ll sz = v.size();
    n = 1; while (n < sz) n *= 2;
    node.resize(2 * n - 1, INF);

    for (ll i = 0; i < sz; i++) node[i + n - 1] = v[i];
    for (ll i = n - 2; i >= 0; i--) node[i] = min(node[2 * i + 1], node[2 * i + 2]);
  }
  void update(ll x, ll val) {
    x += (n - 1);

    node[x] = val;
    while (x > 0) {
      x = (x - 1) / 2;
      node[x] = min(node[2 * x + 1], node[2 * x + 2]);
    }
  }
  ll getmin(ll a, ll b, ll k = 0, ll l = 0, ll r = -1) {
    // [a, b)
    if (r < 0) r = n;
    if (r <= a || b <= l) return INF;
    if (a <= l && r <= b) return node[k];

    ll vl = getmin(a, b, 2 * k + 1, l, (l + r) / 2);
    ll vr = getmin(a, b, 2 * k + 2, (l + r) / 2, r);
    return min(vl, vr);
  }
};
string smax(string x, string y) {
  if (x == y) return x;
  if (x == "inf") return y;
  if (y == "inf") return x;
  if (x == "INF" || y == "INF") return "INF";
  if (x[0] == '-' && y[0] == '-') {
    if (x.size() > y.size()) return y;
    if (x.size() < y.size()) return x;
    if (x.size() == y.size() && x > y) return y;
    if (x.size() == y.size() && x < y) return x;
  }
  if (x[0] == '-') return y;
  if (y[0] == '-') return x;
  if (x.size() > y.size()) return x;
  if (x.size() < y.size()) return y;
  if (x.size() == y.size() && x > y) return x;
  if (x.size() == y.size() && x < y) return y;
}
string smin(string x, string y) {
  if (x == y) return x;
  if (x == "INF") return y;
  if (y == "INF") return x;
  if (x == "inf" || y == "inf") return "inf";
  if (x[0] == '-' && y[0] == '-') {
    if (x.size() > y.size()) return x;
    if (x.size() < y.size()) return y;
    if (x.size() == y.size() && x > y) return x;
    if (x.size() == y.size() && x < y) return y;
  }
  if (x[0] == '-') return x;
  if (y[0] == '-') return y;
  if (x.size() > y.size()) return y;
  if (x.size() < y.size()) return x;
  if (x.size() == y.size() && x > y) return y;
  if (x.size() == y.size() && x < y) return x;
}
vector<pair<ll, ll>> prime_factorization(ll x) {
  vector<pair<ll, ll>> ans(0);
  for (ll p = 2; p * p <= x; ++p) {
    if (!(x % p)) {
      ll e = 0;
      while (!(x % p)) {
        x %= p;
        ++e;
      }
      ans.push_back({ p,e });
    }
  }
  if (x != 1) ans.push_back({ x,1 });
  return ans;
}
ll phi(ll x) {
  const auto& pf = prime_factorization(x);
  ll ans = x;
  for (pair<ll, ll> p : pf) {
    ans *= (p.first - 1);
    ans *= p.first;
  }
  return ans;
}
ll modinv(ll x, ll MOD) {
  ll y = MOD, u = 1, v = 0;
  while (y) {
    ll t = x / y;
    x -= t * y; swap(x, y);
    u -= t * v; swap(u, v);
  }
  u %= MOD;
  if (u < 0) u += MOD;
  return u;
}
ll modpow(ll a, ll n, ll MOD) {
  ll ans = 1;
  while (n > 0) {
    if (n & 1) ans = ans * a % MOD;
    a = a * a % MOD;
    n >>= 1;
  }
  return ans;
}
ll GCD(ll x, ll y) { return (y == 0 ? x : GCD(y, x % y)); }
vector<ll> _f(1000001), _finv(1000001), _inv(1000001);
void Cinit(ll MOD) {
  _f[0] = 1;  _f[1] = 1;
  _finv[0] = 1; _finv[1] = 1;
  _inv[1] = 1;
  for (ll i = 2; i < 1000001; ++i) {
    _f[i] = _f[i - 1] * i % MOD;
    _inv[i] = MOD - _inv[MOD % i] * (MOD / i) % MOD;
    _finv[i] = _finv[i - 1] * _inv[i] % MOD;
  }
}
ll modnCr(ll n, ll r, ll MOD) {
  if (n < r) return 0;
  if (n < 0 || r < 0) return 0;
  return _f[n] * (_finv[r] * _finv[n - r] % MOD) % MOD;
}
ll modnHr(ll n, ll r, ll MOD) {
  return modnCr(n + r - 1, r, MOD);
}
int main() {
  ll N, M;
  cin >> N >> M;
  vector<ll> ans(0);
  while (M) {
    ans.push_back(N / M);
    N = N % M;
    swap(N, M);
  }
  for (ll i = 0; i < ans.size(); ++i) cout << ans[i] << (i == ans.size() - 1 ? "\n" : " ");
}
0