【AtCoder】ABC172-Dで学ぶOEISの使い方
競プロerのみなさんも，そうでないみなさんもこんにちは．
この記事ではAtCoderBeginnerContest 172で出題された D - Sum of Divisors を例にして，OEISの競プロでの活用法を紹介していきます．
OEISとは
OEISとはオンライン整数列大辞典というもので，このページが詳しいですので詳しいことを知りたい方はそちらを御覧ください．
簡単に説明すると，数列を検索することができて，先人たちが発見した公式やそれに関するメモを見ることができるサイトです．
実際に使ってみる
今回扱っていく問題はこちらです．
パット見た感じでは，1からNまでいい感じに素因数分解して計算したらよさそう，と思いますが間に合いません．
なので工夫しなくてはいけないのですが，OEISを使うことでこの問題は解決できます．
まずは検索する数列を用意するために，プログラムを書くなど愚直に計算するなどして第8,9項あたりまで求めます．
実際に計算したものがこちらです．（はい！？）
というわけでOEISに実際にアクセスして検索していきます．
ところで，これは一般的に言えることなのですが，数列を検索する際は第3項めあたりから5,6項を入れて検索するといいです．Hintsにも書いてあります．*1
なので，求めた数列を第3項からカンマ区切りで入力して検索してみると，数列が出てきてくれます．
数列のタイトルも，「Sum of k*d(k) over k=1,2,...,n, where d(k) is the number of divisors of k.」と，問題が問うていることと一緒です．この情報を引き当てたのはとてもデカイです．
そしてありがたいことに，公式まで掲載されています．
今回の場合では，上から三番目の公式を使うことで整数の範囲かつ計算量もの範囲で簡単に解くことができそうです．
ここまでくれば，書いてあるとおりに実装するだけで問題はとけたようなものです．
OEISのさらなる使い方?
今回扱った問題は，そのまま数列を検索することでOEISから出てきますが，強い方の記事によると，二次元を一次元に落としたり，全体を2で割るなどしないと出てこないような数列もあるようです．
扱ったサイト
OEIS: https://oeis.org/
扱った問題: https://atcoder.jp/contests/abc172/tasks/abc172_d
ABCのD問題のような比較的難しく思える問題でも，OEISを使って検索することで答えが出ることを学べました．
