解法一覧 - ぺんぎんノート

たとえば11001100...という1と0からなる数列の、$N$番目までの1の個数を数えるときに、周期性のある部分の個数を$C$とおくことで、1の個数を$C \times 2 + \min((N - C \times 4), 4)$という一つの式で表せます（$\min$の部分はAdhocな考察が必要です）。そして$C$についても、$C = \lfloor N / 4 \rfloor$という簡単な計算で求めることができます。

next_permutation()を使って$N!$通りの探索を行います。

以下の数式を利用することで、計算量を落とせることがあります。 $$\sum_{i=1}^m (a_i + b_i) = \sum_{i=1}^m a_i + \sum_{i=1}^m b_i$$ $$\sum_{i=1}^m \sum_{j=1}^n a_{ij} = \sum_{j=1}^n \sum_{i=1}^m a_{ij}$$ $$\sum_{i=1}^m \sum_{j=1}^n a_ib_j = \sum_{i=1}^m a_i \sum_{j=1}^n b_j $$

$1 \le N \le 10^9$を満たす$N$の、約数の個数の最大は$1344$個（$N = 73513440$）。この少なさを利用して計算量を落とせることがあります。ちなみに、約数の列挙は$O(\sqrt N)$でできます。