🐷

ARC 051 | B - 互除法

2020/12/06に公開

競プロ

gcd

tech

問題

考えたこと

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してから解答みたら

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

ARC 051 | B - 互除法

問題

考えたこと

コード

ACしてから解答みたら

参考

Discussion