How Many Sets III (ZOJ Problem Set - 3558)

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3558

問題

略

解法

答えは[tex:\sum_{a=1}^{n-1}\sum_{x=1}^{{\rm floor}*1ので間に合う。

*1:n-1)/a)}(n-ax)]となる。高速化するためにまず内側のsumを等差数列の和の公式で展開する。外側のsumはfloorがあるため展開できないが ${\rm floor}((n-1)/a)$ が同じ部分をまとめて展開すれば良い。実際 ${\rm floor}((n-1)/a)$ の種類は $O(\sqrt{n})$ 個しか無い(( ${\rm floor}((n-1)/a)$ が $\sqrt{n}$ 以上になるのは $a\le\sqrt{n}$ の時で、以下の時はもちろん $\sqrt{n}$ 個しか無い。