問題 atcoder.jp 整数からなる公差 1の等差数列のうち、総和が Nであるものはいくつあるでしょうか？ 解法 等差数列の和の公式 初項が a，公差が d，項数が n Sn = n/2(2a + (n-1)*d) d = 1なので Sn = n/2(2a + (n-1)) 2Sn = n(2a + (n-1)) なので、nは2Sn…

問題 atcoder.jp 解法 数列Aの中のAiの倍数を配列fをつくって、あらかじめカウントしておく。 f[i]はIの約数の数が入る。 これができてしまえば、Aiの数値の約数はf[Ai]を参照すればわかる。 f[Ai]が1ならば、Aiの約数は自分自身しかないので、数列Aの中にAi…

問題 atcoder.jp 解法 1 〜 Nまでの約数を配列に保存する方針。 1の倍数、2の倍数、3の倍数……と各配列に1づつ足していく。 この約数を求める計算量は Nを外にだして Σ部分は調和級数になるので、だいたいlogNになる。 ゆえに計算量はO(NlogN)とのこと。 約数…

問題 atcoder.jp 解法 とにかく入力例とか問題の内容読むと「これ約数の問題っぽくない！？」と悟れという問題のよう。 最大公約数がモンスターのHPの最小値になるので、これを求めればよい。 3つ以上のパラメータの最大公約数の求め方が実装例(Python3.8系)…

問題 atcoder.jp 解法 約数列挙問題。 たとえば20の約数を調べるときに、20%2は余り0。 よって約数とわかるが、20/2 = 10もついでにわかる。 こうしておくと、ループは20の平方根までで済み、だいぶ計算量をおさえることができる。 ループ最後あたりで、答え…

素数系の問題っていうのがAtCoderであるみたいで、やったことないので探してやってみました。 atcoder.jp Python ACコード 基本はまやん氏の解法のコードを元にPythonで実装しました。 blog.hamayanhamayan.com エラトステネスのふるいで10**5以下の素数を、…