【ABC148 C】「Snack」を解く【Python3】

abc148c

コンテスト一覧へ

 

人数がA人かB人だった場合、どちらでも均等に配れるお菓子の数を答える問題です。

入力は整数のA,Bのみです。二つ数字の最小公倍数が答えとなります。

最小公倍数をそのまま調べでも良いのですが、最大公約数から求めることもできます。

(最小公倍数) = A * B / (最大公約数)

 

最小公倍数と最大公約数はそれぞれ、

  • 最小公倍数はlcm(「least common multiple」の略)
  • 最大公約数はgcd(「greatest common divisor」の略)

となり、言語によっては関数が用意されている場合があります。

python3は、3.5以降でmathモジュールにgcd()関数があります。

ただ、AtCoderのpython3は、3.4.3なので、mathモジュールにgcd()関数はありません。

代わりにfractionsモジュールにgcd()関数があるので、そちらを使用します。

提出
from fractions import gcd
a, b = map(int, input().split())

ans = a * b // gcd(a, b)
print(ans)

 

gcd()関数を知らなかった場合でも、for文を用いて最小公倍数を求めることができます。

提出
a, b = map(int, input().split())

n = max(a, b)
m = min(a, b)
ans = 0

for i in range(1, m + 1):
    ans = n * i
    if (ans) % m == 0:
        print(ans)
        exit(0)

入力された整数の大きい方(n)に数字を掛けていき、小さい方(m)で割り切れる数字が出たら、それが答えです。

if文の最後にexit(0)を使ってプログラムを終了させます。これをしないと公倍数が出力され続けてしまいます。

【ABC148】解説記事

コンテスト一覧に戻る

コメントを残す

メールアドレスが公開されることはありません。