Kazun の競プロ記録

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

AtCoder Beginner Contest 254 D問題 Together Square

AtCoder ABC ABC254 D問題 400 pts

問題

提出解答

問題の概要

次を満たす $1$ 以上 $N$ 以下の整数の組 $(i,j)$ の個数を求めよ.

$i \times j$ が平方数になる.

制約

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

解法 1

正の整数 $n$ と素数 $p$ に対して, $\nu_p(n)$ を

$\nu_p(n):=\max \{k \in \mathbb{Z}; ~p^k ~|~ n \}$

と定義する. つまり, $n$ を $p$ で割り切れる最大の回数とする.

このとき, $\mathbb{P}$ を素数全体の集合としたとき, 正の整数 $n$ に対して, 有限個の $p \in \mathbb{P}$ を除いて $\nu_p(n)=0$ であること, 及び,

$\displaystyle n=\prod_{p \in \mathbb{P}} p^{\nu_p(n)}$

であることに注意する.

ここで, 整数同士の積と素因数分解について, 以下が成り立つ.

$m,n$ を正の整数とする.

$\displaystyle mn=\prod_{p \in \mathbb{P}} p^{\nu_p(m)+\nu_p(n)}$
$n$ が $k$ 乗数 $\iff$ 任意の素数 $p \in \mathbb{P}$ に対して, $\nu_p(n)$ は $k$ の倍数

よって, 積が平方数であるかどうかは各整数 $n$ における $\nu_p(n)$ の偶奇が重要であることがわかる.

解法 2

このことから, 正の整数 $n$ と素数 $p$ に対して, $\mu_p(n)$ を

$\mu_p(n):=\begin{cases} 0 & (\nu_p(n): {\rm even}) \\ 1 & (\nu_p(n): {\rm odd}) \end{cases}$

とする. そして, $\rho(n)$ を

$\displaystyle \rho(n)=\prod_{p \in \mathbb{P}} p^{\mu_p(n)}$

と定める.

すると, 正の整数 $m,n$ に対して, 以下は同値になる.

$mn$ は平方数
全ての素数 $p$ に対して, $\nu_p(m)+\nu_p(n)$ は偶数
全ての素数 $p$ に対して, $\mu_p(m)+\mu_p(n)$ は偶数
全ての素数 $p$ に対して, $\mu_p(m)=\mu_p(n)$ である.
$\rho(m)=\rho(n)$

このことから, $\rho(1), \rho(2), \dots, \rho(N)$ にある $k$ の個数を $\chi_\rho(k)$ としたとき, 任意の整数 $n$ に対して, $\rho(n) \leq n$ であるので, 求めるべき答えは

$\displaystyle \sum_{k=1}^N \chi_{\rho}(k)^2$

である.

計算量は $\rho(n)$ を求めるための $\nu_p(n)$ の計算がボトルネックになる. 結局 $\nu_p(n)$ は素因数分解で求めることになるので, $O(N \sqrt{N})$ で計算できる. そして, $,1,2, \dots, N$ の素因数分解をすることになるので, 事前に $1,2, \dots, N$ における最小素因数を求めることにより, 全体で $O(N \log N)$ に高速化できる.