問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

正の整数のクアドラプル $(A,B,C,D)$ に対して, $AB+CD=N$ を満たすのはいくつか?

制約

$2 \leq N \leq 2 \times 10^5$

解法

$AB+CD=N$ を満たすクアドラプル $(A,B,C,D)$ について, $AB$ の値で場合分けをする. ここで, $A,B,C,D$ は全て $N$ 以下であることがわかる.

$X=1,2, \dots, N$ に対して, $AB=X$ を満たす整数のペア $(A,B)$ の数は, $X$ を約数列挙して求める方法や, $A=1,2, \dots, N, 1 \leq B \leq \dfrac{N}{A}$ の範囲で $(A,B)$ を動かし, 一気に求めるなどがある.

$AB=X$ を満たす正の整数のペア $(A,B)$ の数を $T_X$ としたとき, 求めるべきは

$\displaystyle \sum_{X=1}^{N-1} T_X T_{N-X}$

である.

Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 292 C問題 Four Variables

問題

提出解答

問題の概要

制約

解法