betrue12 https://blog.hatena.ne.jp/betrue12/ ARMERIA https://betrue12.hateblo.jp/ AOJ プログラミング 競技プログラミング お題箱より。 Aizu Online Judge 解法 最小公倍数や最大公約数は、素因数ごとに「重複度の最大値/最小値」を取るという観点で捉えると考えやすくなることがあります。 の最小公倍数（LCM）は、全ての素数 について各要素における の重複度の最大値 を求め、 を全て掛け合わせたものである。 の最大公約数（GCD）は、全ての素数 について各要素における の重複度の最小値 を求め、 を全て掛け合わせたものである。 この観点で問題を捉えるために、まず を素因数分解します。 の相異なる素因数を とし、それぞれの重複度を とします。 整数列 の要素のLCMが になる必要十分条件は、以下の条件を全… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fbetrue12.hateblo.jp%2Fentry%2F2020%2F11%2F03%2F205320" title="Waseda University Programming Contest 2020 E: LCM Count (AOJ 3155) - ARMERIA" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.user.blog.st-hatena.com/default_entry_og_image/106916089/1592411661884548 Hatena Blog https://hatena.blog 2020-11-03 20:53:20 rich https://betrue12.hateblo.jp/entry/2020/11/03/205320 1.0 100%