🐷

ARC 051 | B - 互除法

1 min read

問題

https://atcoder.jp/contests/arc051/tasks/arc051_b

考えたこと

int counter = 0;
int gcd(int a, int b) {
  if (b == 0) return a;
  counter++;
  return gcd(b, a%b);
}

上記なのでb = 0のときにストップしカウントは0になる。
その時のaを1とおくとgcdの動作は以下のようになる。

カウンタの値をiとしてa, bそれぞれをa[i], b[i]とするとb[i] = a[i-1]である。a[i]b[i]で割ったときにb[i-1]をあまりとする値なのでa[i] = a[i-1] + b[i+1]とすればいい。

コード

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

int main() {
  ll k;
  cin >> k;
  vector<pair<ll, ll>> v(41);  // {a, b}
  v[0] = {1, 0};
  v[1] = {2, 1};
  for (int i = 2; i <= k; i++) {
    v[i].second = v[i - 1].first;
    v[i].first = v[i - 1].second + v[i].second;
  }
  cout << v[k].first << " " << v[k].second << endl;
}

ACしてから解答みたら

フィボナッチとあり、たしかにとなった。

参考

https://atcoder.jp/contests/arc051/tasks/arc051_b/editorial

Discussion

ログインするとコメントできます