AtCoder Beginner Contest 253 D問題 FizzBuzz Sum Hard

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

$1$ 以上 $N$ 以下の整数のうち, $A$ の倍数でも $B$ の倍数でもないような整数全ての総和を求めよ.

制約

$1 \leq N,A,B \leq 10^9$

解法

集合 $U,X,Y$ を

$U$ : $1$ 以上 $N$ 以下の整数全体の集合
$X$ : $1$ 以上 $N$ 以下の整数のうち, $A$ の倍数であるもの全体の集合
$Y$ : $1$ 以上 $N$ 以下の整数のうち, $B$ の倍数であるもの全体の集合

とする.

すると, 包除原理から,

$\displaystyle \sum_{x \in U \setminus (X \cup Y)} x=\sum_{x \in U} x-\sum_{a \in X} a-\sum_{b \in Y} b+\sum_{c \in X \cap Y} c$

である.

ここで, 整数 $n$ に対して, $n$ が $A$ の倍数かつ $B$ の倍数であることと, $n$ が $\operatorname{lcm}(A,B)$ の倍数であることが同値になる. そして, 任意の整数は $1$ の倍数であることを利用すると, $1$ 以上 $N$ 以下の整数における $m$ の倍数の総和を $g_m(N)$ と書くことにすると,

$\displaystyle \sum_{x \in U} x=g_1(N)$
$\displaystyle \sum_{a \in X} a=g_A(N)$
$\displaystyle \sum_{b \in Y} b=g_B(N)$
$\displaystyle \sum_{c \in X \cap Y} c=g_{\operatorname{lcm}(A,B)}(N)$

であるから,

$\displaystyle \sum_{x \in U \setminus (X \cup Y)} x=g_1(N)-g_A(N)-g_B(N)+g_{\operatorname{lcm}(A,B)}(N)$

となる.

最後に, $g_m(N)$ の求め方を考える. $1$ 以上 $N$ 以下の整数は $1$ 以上 $\displaystyle \left \lfloor \dfrac{N}{m} \right \rfloor$ 以下の整数を用いて, $mj$ と表せ, 逆に, このように表せる整数は全て $1$ 以上 $N$ 以下の $m$ の倍数である.

よって, $\displaystyle p:=\left \lfloor \dfrac{N}{m} \right \rfloor$ とすると,

$\displaystyle g_m(N)=\sum_{j=1}^p mj=m \sum_{j=1}^p j=j \cdot \dfrac{p(p+1)}{2}$

である.

$\displaystyle \operatorname{lcm}(A,B)=\dfrac{AB}{\gcd(A,B)}$ であることに注意すると, $\gcd(A,B)$ を求めるために $O(\log \min(A,B) )$ 時間かかり, それ以外では定数時間で処理できる. よって, $O(\log \min(A,B) )$ 時間で求めることができた.

Kazun の競プロ記録

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

AtCoder Beginner Contest 253 D問題 FizzBuzz Sum Hard

問題

提出解答

問題の概要

制約

解法