結果
問題 | No.1794 Continued Fraction |
ユーザー |
![]() |
提出日時 | 2021-12-24 16:41:08 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 989 bytes |
コンパイル時間 | 350 ms |
コンパイル使用メモリ | 41,928 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-19 15:19:39 |
合計ジャッジ時間 | 1,335 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
/* -*- coding: utf-8 -*- * * 1794.cc: No.1794 Continued Fraction - yukicoder */ #include<cstdio> #include<algorithm> using namespace std; /* constant */ const int MAX_L = 62; /* typedef */ /* global variables */ int as[MAX_L]; /* subroutines */ template <typename T> T gcd(T m, T n) { // m > 0, n > 0 if (m < n) swap(m, n); while (n > 0) { T r = m % n; m = n; n = r; } return m; } void reduce(int &n, int &m) { if (n > 0 && m > 0) { int g = gcd(n, m); n /= g, m /= g; } } /* main */ int main() { /* Let xi=ai+1/x{i+1}, xL=aL -> n/m = x0 = a0+1/x1 -> 1/x1 = n/m-a0 = (n-m*a0)/m -> x1 = m/(n-m*a0) */ int n, m; scanf("%d%d", &n, &m); reduce(n, m); int l = 0; while (n > 0 && m > 0) { int d = n / m; n -= m * d; as[l++] = d; reduce(n, m); swap(n, m); } while (l > 0 && as[l - 1] == 0) l--; for (int i = 0; i < l; i++) printf("%d%c", as[i], (i + 1 < l) ? ' ' : '\n'); return 0; }