問題

https://beta.atcoder.jp/contests/ddcc2019-qual/tasks/ddcc2018_qual_c

考え方

条件を整理すると、以下を満たすような数え上げである。

$(P_1, ..., P_{10})$ の最大値を $P_{max}$
$(Q_1, ..., Q_{10})$ の最大値を $Q_{max}$ とすると

$1 \le P_{max} \times Q_{max} \le N$

である。 $P_{max}$ を全探索し $P_{max} = c$ とするとき $Q_{max}$ は $\displaystyle Q_{max} = \lfloor\frac{N}{c}\rfloor$ と一意に定まる。また $(P_1, ..., P_{10})$ で $P_{max} = c$ となるような組み合わせの数は $c^{10} - (c-1)^{10}$ である。 $P$ の組み合わせが定まった時に $Q$ の組み合わせは $\displaystyle Q_{max} \le \lfloor\frac{N}{c}\rfloor$ であるような組み合わせの数であるから $Q$ の組み合わせの数は $\displaystyle \lfloor\frac{N}{c}\rfloor^{10}$ である。

よって $P_{max} = c$ であるような組み合わせの数は $\displaystyle c^{10} - (c-1)^{10} \times \lfloor\frac{N}{c}\rfloor^{10}$

あとは $1 \le c \le N$ の範囲で $c$ を探索し、それぞれ足せばよい。

Submission #3649014 - DISCO presents ディスカバリーチャンネルコードコンテスト2019 予選

どこに着目して考察するべきだったか

$P(P_1, ..., P_{10}),Q(Q_1, ..., Q_{10})$ と $2$ 変数出てくるがそれぞれの最大値のみが重要であり、一方の最大値 $c$ を決めうちすると、もう片方の最大値は $\displaystyle \lfloor\frac{N}{c}\rfloor$ と決まるので、一方の最大値を全探索すべき。片側だけ全探索すれば、重複なくすべての組み合わせを求められる。