【競プロ精進ログ】ABC148-C

zuka

ABCをコツコツ解いていきます。

本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。

これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。

本記事の概要

Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回はABC148-C「Snack」です。

ポイント

最小公倍数を求める問題です。最小公倍数$\mathrm{lcm}(A, B)$は，$A$と$B$の最大公約数を$\mathrm{gcd}(A, B)$とおけば，以下のように表されます。

直感的に説明は可能です。$A$と$B$が互いに素である場合には，$A\times B$が最小公倍数である感覚は皆さんのなかにあると思います。問題は，$A$と$B$が公約数を持っている場合です。そのときは，$A\times B$では公約数が余分にかけられてしまいます。

その余分にかけられた公約数を集めれば，最大公約数になることはイメージつきますでしょうか。ですので，余分にかけられたゴミを除くためには，最大公約数で割ってあげればOKなのです。最大公約数の解説や実装方法は，以下の記事を参考にしていただければと思います。

あわせて読みたい

【c++で楽しく実装！】ユークリッドの互除法 本記事では，ユークリッドの互除法の簡単な解説と実装例をお伝えしていきます。使用言語はc++です。その他の競技プログラミング関連の記事は，以下の目次をご覧ください...

実装

#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;
typedef long long ll;

// オーバーフローに注意してlong longで定義する
ll gcd(ll a, ll b) {
  return b != 0 ? gcd(b, a % b) : a;
}

int main(){
  // オーバーフローに注意してlong longで定義する
  ll A, B;
  cin >> A >> B;
  // 最小公倍数は式(1)で求められる
  cout << A * B / gcd(A, B) << endl;
}