hamayanhamayan https://blog.hatena.ne.jp/hamayanhamayan/ はまやんはまやんはまやん https://blog.hamayanhamayan.com/ 競技プログラミング https://beta.atcoder.jp/contests/abc112/tasks/abc112_d 解法 https://beta.atcoder.jp/contests/abc112/submissions/3348509全ての要素の公約数としてgがある場合を考える。 全ての要素がgの倍数になれば、公約数がgになる。 まず、満たすべき条件としてMがgで割り切れる必要がある。 M/g個のgを各要素に分配していくことを考えるが、各要素最低1つは割り当てられる必要がある。 よって、N≦M/gが満たされる必要がある。 公約数gを全探索するが、これはMの約数になっているので、そんなに量がない… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fblog.hamayanhamayan.com%2Fentry%2F2018%2F10%2F06%2F233701" title="Partition [AtCoder Beginner Contest 112 D] - はまやんはまやんはまやん" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2018-10-06 23:37:01 rich https://blog.hamayanhamayan.com/entry/2018/10/06/233701 1.0 100%