Python3で解く AtCoder Beginner Contest 148 C - Snack
目次
概要
問題
1. 人
人でも均等にお菓子を分けられるような最小のお菓子の数は？
制約
は整数
解くときに考えた内容
- 単純に
の最小公倍数を求める。
- 最小公倍数を求めるには。最大公約数が必要。
- 以下の手法を実装する
最大公約数の求め方
ユークリッドの互除法
ちなみにPythonには最大公約数がすでに実装されている。
- Python3.4ならfractions.gcd、3.5以降はmath.gcdにあるがここでは、敢えて実装する。
- 再帰的に実装する。（コードを見ればかなりシンプル）
最小公倍数は以下の関係から実装する。
最小公倍数の求め方
正整数と
bの最大公約数(gcd)と最小公倍数(lcm)の間には以下の関係がある。
なので単純に
コード
import sys sys.setrecursionlimit(10**7) def gcd(a, b): if b == 0: return a else: return gcd(b, a%b) def lcm(a, b): return int(a / gcd(a, b)) * b a, b = map(int, input().split()) ans = lcm(a, b) print(ans)
書籍
最近ポチった書籍
- 実用的でないPythonプログラミング
実用的でないPythonプログラミング: 楽しくコードを書いて賢くなろう!
- 作者:ヴォーン,リー
- 発売日: 2020/08/12
- メディア: 単行本
バカ売れしているのか、アマゾンでは値段があがっている。自分は、予約していたのに来ないので、楽天で購入した。 内容としては、面白いテーマの物が多く、pygletなどを使って描画もあるような内容が結構推されているが、アルゴリズムに関する内容もある。特に前半は文字列を操作して暗号解読であったり、アナグラム・回文といったものが扱われているので勉強になる。遺伝的アルゴリズムも面白く金庫破りの実装は非常に参考になった。
- 問題解決力を鍛える!アルゴリズムとデータ構造
けんちょんさんこと、大槻さんの書籍である、「問題解決力を鍛える!アルゴリズムとデータ構造」 ご本人の記事の中で難易度は、螺旋本ということで初学者でも結構読みやすいのではないかと期待。（というのもけんちょんさんの記事はC++に疎い自分でも、その思考プロセスを学べるくらい丁寧に書かれているので）
投稿時点では、まだ発売前だけど、すでにベストセラー。予約しておかないとすぐ手元に来ないかも!?と思って速攻ポチった。
問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)
- 作者:大槻 兼資
- 発売日: 2020/10/02
- メディア: 単行本（ソフトカバー）
アルゴリズムの参考書籍
- プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
いわゆる、螺旋本。Aizu Online Judgeの問題を題材に解説されている。自分としては、 Aizu Online Judgeは最近はβ版運用中で、構成がアルゴリズムの項目ごとに問題がタグ付けされているようなイメージで、ここら辺弱いから集中的にやってみようっていう感じでできるので、いいと思っている。（AtCoderもそんな感じのリスト作って欲しい） ただ、この書籍はC++で書かれているのでPythonでやる場合はあくまでもその過程の考え方を参考にし自分で実装する必要がある。（AOJも解いているので、記事にしていこうかなぁ）
