Sigma Divisors

解説

$S_x(N)$ の個数 $|S_x(N)|$ を考えてみましょう。整数 $i$ について、$\displaystyle\sum_{j=1}^{i}j = \frac{i(i+1)}{2}$ より、この値が $x$ の倍数であるためには $i(i+1)$ が $2x$ の倍数、つまり$i(i+1)\equiv0\mod 2x$ となれば良いです。

では、このような $i$ を探してみます。 ここで、唐突に $2x$ を素因数分解し、その結果を $\displaystyle 2x = \prod_{k=1}^{K}{p_k^{e_{k}}}$ とします。このとき、任意の $k$ について、

$i(i+1) \equiv 0 \longleftrightarrow i \equiv 0,-1 \mod p_k^{e_{k}}$ が成り立ちます。$(i$ と $i+1$　は互いに素であることから$)$

一方で、$i(i+1) \equiv 0 \mod 2x \longleftrightarrow \forall k, i(i+1) \equiv 0 \mod p_k^{e_{k}}$ が成り立つため(検証は追記にて)、

それぞれの $k$ について $i \equiv 0,-1 \mod p_k^{e_{k}}$ が成り立てばよいと分かります。このような条件を満たす $i$ は、各 $k$ について　$i \equiv 0$ と $i \equiv -1$ $(\mod p_k^{e_{k}})$ の $2$ 通りから選ぶので、合計で $2^K$ 通りです。これら $2^K$ 通りの $i\mod 2x$ を列挙し、列挙した $i$ それぞれについて $1$ から $N$ までの中に$2x$ で割ったあまりが $i$ となるような整数が何個あるかを求めることで $|S_x(N)|$ を求めることができます。

計算量について考えます。まず、素因数分解は試し割り法を用いて $O(\sqrt{a})$ です。 $2^K$ 通りの $i$ の値の列挙に関して、各 $i$ の構築において拡張ユークリッドの互除法を用いた中国剰余定理に $O(K\log{a})$ かかるため、列挙全体で $O(2^KK\log{a})$ かかります。ここで、 $K$ の上限は、$2 \times a$ までの整数のうち、最も多くの素因数をもつ整数における素因数の個数の上限であり、$S_p = 2⋅3⋅5⋅7⋅11⋅13⋅17⋅19⋅23⋅29⋅31 < 2 \times 10^{12} < S_p \times 37$ から $K \leq 11$ であるので、問題ありません。よって全体として $O(\sqrt{a}+2^KK\log{a})$ となり、これは十分高速です。

追記

• $i(i+1) \equiv 0 \mod 2x \longleftrightarrow \forall k, i(i+1) \equiv 0 \mod p_k^{e_{k}}$

まず $\longrightarrow$ は明らかです。$i(i+1)$ が $2x$ の倍数であるとき、任意の $k$ について $p_k^{e_{k}}$ は $2x$ の約数より、$i(i+1)$ は $p_k^{e_{k}}$ の倍数となります。 また、$\longleftarrow$ も明らかです。任意の $k$ について $i(i+1)$ を $p_k^{e_{k}}$ が割り切れるとき、$p_k^{e_{k}}$ 同士は互いに素であるので、それらの積である $2x$ は $i(i+1)$ で割り切ることができます。