baitop https://blog.hatena.ne.jp/baitop/ バイトの競プロメモ https://baitop.hatenadiary.jp/ B - GCD Sequence問題概略 要素数がNで互いに異なる整数であり、どの要素もそれ以外の合計との最大公約数が1ではなく、すべての要素の最大公約数が1であり、すべては30000以下である物を求めよ 3解法 ある要素とそれを除く要素の合計の最大公約数と、ある要素と全体の合計の最大公約数は等しい。 よって、すべての要素の最大公約数が1であり、すべての要素に対して全体の合計の最大公約数が1で無いものを考えれば良い。 そう考えると、合計に対して全要素に約数をもたせたいと考えたくなる。しかし、全体の最大公約数を1にするため、約数は2種類必要だとわかる。小さい方がいいので2,3を使いたくなるが、制… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fbaitop.hatenadiary.jp%2Fentry%2F2018%2F09%2F13%2F175608" title="B - GCD Sequence AtCoder Grand Contest 022 - バイトの競プロメモ" 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-09-13 17:56:08 rich https://baitop.hatenadiary.jp/entry/2018/09/13/175608 1.0 100%