う え き ぷ に き あ く ん 笑 Advent Calendar 2021 6日目です
この記事について
AtCoder Beginner Contest（以下、ABC）に参加する際に最低限理解する必要があると感じた数学的知識について解説します。内容としては、
・絶対値
・1からnまでの和
・冪乗
・指数法則
・素因数分解
・ユークリッドの互除法
・三平方の定理
となっています。
注意点として、簡潔に説明するため、用語などの説明や証明などを省いています。より深い理解を得たい場合は、別途調べることをお勧めします。（もし内容に不備があった場合、教えていただけるととっても喜び、修正させていただきます！）
絶対値
絶対値とは、ある数の数直線上での0との距離のことです。
ここで、xを任意の数とします。また、絶対値は$ |x| $という形で表されます。（競技プログラミングでは、|S|は文字列Sの長さという意味で使われることもあります）
xが正のとき、$ |x| = x $
xが負のとき、$ |x| = -x $
xが0のとき、$ |x| = 0 $
xが$ i $（$ \sqrt{-1} $）のとき、$ |x| = 1 $
となります。
以下、実例です。
$ |2| = 2 $
$ |-2| = 2 $
$ |-5.1| = 5.1 $
$ |-(-425)| = |425| $
また、複素数$ a + bi $の絶対値は$ \sqrt{a^2 + b^2} $と定義されています。
ABCでは、
建物が二つある。それぞれの高さを$ H_1 $, $ H_2 $としたとき、その差はいくらか。
といった風に出題されることがり、この答えは$ H_1 $と$ H_2 $の大小関係に左右されず、$ |H_1 - H_2| $（あるいは$ |H_2 - H_1| $）となります。
１からnまでの和
nが0以上のとき、１からnまでの和は$ \frac{n(n + 1)}{2} $で求めることができます。
なぜかというと、$ 1 + n = 2 + n-1 = 3 + n-2 = ... = n + 1$が成り立つことより、
n+1をn回足した数は、1〜nをそれぞれ2回ずつ足したことになるため、それを2で割った数は1からnまでの和となるからです。
この式の嬉しいところは、1〜nまでの数を順に足していくことを考えるとO(n)となってしまいますが、この式を使うことでO(1)となります。
また、$ 0 ≤ L ≤ R $のL,Rについて、L〜Rの和を求めるとき、$ [Rまでの和] - [L-1までの和] $で求めることができます。
以下、実例です。
$ n = 4 $
$ \frac{n(n + 1)}{2} = \frac{4 × 5}{2} = 10 $
$ n = 100 $
$ \frac{n(n + 1)}{2} = \frac{100 × 101}{2} = 5050 $
$ L = 4, R = 7 $
$ \frac{R(R+1)}{2} - \frac{L(L - 1)}{2} = 28 - 6 = 22 $
ABCでは、$ 1 ≤ i,j ≤ N $を満たす$ (i, j) $の組の数を求める必要があるときなどにも使えます。
冪乗
冪乗とは、$ a^b $のような形（あるいは、a^bの形）で表された数式で、aをb回かけることを表します。また、$ a^{-b} $は$ \frac{1}{a^b} $となり、$ a^\frac{c}{b} $は$ \sqrt[b]{a^c} $（b乗すると$ a^c $になる数）を表しています。そして、0乗すると、どんな数でも（0でも負でも）1になります。
以下、実例です。
$ 2^4 = 2 × 2 × 2 × 2 = 16 $
$ (-3)^2 = (-3) × (-3) = 9 $
$ 4^\frac{1}{2} = \sqrt[2]{4} = \sqrt{4} = 2 $
$ 27^\frac{-2}{6} = 27^\frac{-1}{3} = \frac{1}{\sqrt[3]{27}} = \frac{1}{3} $
$ 5^0 = 1 $
$ 1^{5000} = 1 $
$ 0^{12345} = 0 $
ABCに限りませんが、様々な計算で使用します。
指数法則
先に解説した冪乗に関連した法則で、
$ a^b × a^c = a^{b + c} $
$ a^b ÷ a^c = a^{b - c} $
$ (a^b)^c = a^{bc} $
$ (ab)^c = a^c × b^c $
というものです。
主に計算量を確かめる際に使用します。
素因数分解
素因数分解とは、ある正の整数を素数の積に置き換えることです。また、1は素数ではないため、素数の積で表すことができません。そのため、例外的に1を素因数分解すると1になる、と定義されています。
以下、実例です。
$ 10 = 2 × 5 $
$ 100 = 2 × 2 × 5 × 5 = 2^2 × 5^2 $
$ 999 = 3 × 3 × 3 × 37 = 3^3 × 37 $
直接問題中に出てくることは少ないですが、様々な問題で素因数分解の考え方が重要になってくることがあります。
ちなみに、ある正整数Nの約数の数は素因数分解したとき、それぞれの素数の羃指数+1を掛けた分だけ存在します。
例えばN = 20のとき、$ N = 2^2 × 5 $なので、$ (2 + 1) × (1 + 1) = 6 $個存在します。実際、20の約数は1, 2, 4, 5, 10, 20であり、6個です。
最大公約数・最小公倍数
そもそも公約数・公倍数とは、ある数a, bがあるとき、公約数は絶対値でaとbのどちらも割り切れる数, 公倍数は絶対値がaとbのどちらの倍数でもある数です。公約数・公倍数ともにaまたはbを含むことができます。
最大公約数はgcdと呼ばれ、aとbの公約数の内最大のものを指します。片方が0のとき、gcdはもう片方の数、両方が0のときは定義されていませんが、プログラミング言語では基本的に0になるようです。また、aとbの最大公約数を$ gcd(a, b) $と表すこともあります。
最小公倍数はlcmと呼ばれ、aとbの公倍数のうち正の最小の数を指します。gcdと同じように、aとbの最小公倍数を$ lcm(a, b) $と表すことがあります。また、$ lcm(a, b) = \frac{a × b}{gcd(a, b)} $と計算することができます。
複数の数に対するgcdは、例えば数をa, b, c, dとするとき、
$ A = gcd(a, b) $を求める
$ B = gcd(A, c) $を求める
$ C = gcd(B, d） $を求める
という手順で求めることができ、Cがa, b, c, dのgcdとなります。lcmの場合も同様に$ lcm(lcm(lcm(a, b), c), d) $という風に求めることができます。
ABCでは、単純に最大公約数・最小公倍数を求めるときやある数同士が互いに素かどうか（$ gcd(a, b) = 1 $のとき、aとbは互いに素です）を調べるなどの用途で必要になる考え方です。
ユークリッドの互除法
aとbの最大公約数を求めたいときに使うことができる知識です。使いすぎてもはや普通の最大公約数の求め方を覚えていません。
手順を説明していきます。ここでは、0を含むときの手順を省略しています。
手順
- aをbで割りきったときの余りをrとする
- rが0のとき、bが最大公約数となる → 終了
- aをbで、bをrで置き換える
- 1に戻る
以下、実例で手順を辿ります。
$ a = 123, b = 456 $
$ 123 ÷ 456 = 0 $ 余り $ 123 $（余りが0でないので続ける）
$ 456 ÷ 123 = 3 $ 余り $ 87 $
$ 123 ÷ 87 = 1 $ 余り $ 36 $
$ 87 ÷ 36 = 2 $ 余り $ 15 $
$ 36 ÷ 15 = 2 $ 余り $ 6 $
$ 15 ÷ 6 = 2 $ 余り $ 3 $
$ 6 ÷ 3 = 2 $ 余り $ 0 $（余りが0なので答えは3）
よって、
$ gcd(123, 456) = 3$
実装例(Python3)を乗せます。※Python3ではmathライブラリにgcd関数として実装されているため、そちらを使用した方が楽に実装ができます
def gcd(a, b):
a = abs(a)
b = abs(b)
# 0が含まれるときの処理
if a == b == 0:
return 0
if a == 0:
return b
if b == 0:
return a
while 1:
r = a % b
if r == 0:
return b
break
else:
a = b
b = r
計算量はO(log min(a, b))となります。
非常に大きな数同士($ 10^{18}と10^{15} $など)の最大公約数を求めるときに使用します（実際は、小さい数同士でもほとんどの場合で使用します）。
三平方の定理
三平方の定理を使うことで、直角三角形の斜辺の長さを求めることができます。
斜辺をa、 それ以外の辺をb, cとすると、
$ a = \sqrt{b^2 + c^2} $
となります。これを応用すると、ある点とある点の距離を求めることができます。
例えば、$ (x_1, y_1) $と$ (x_2, y_2) $の距離Dは
$ D = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2} $（1と2を逆にしてもいいです）
となります（これをユークリッド距離と言います）。
なぜかというと、$ |x_1 - x_2| $はそれぞれの座標のx座標の差、$ |y_1 - y_2| $はy座標の差となり（2乗するので、2点間の距離を求めるときには絶対値を取る必要はありません）、このx, y座標の差を直角三角形の斜辺以外の辺の長さとすることで、2点間の距離を求めることができるというわけです。ちなみに、$ (x_1, y_1, z_1) $と$ (x_2, y_2, z_2) $の距離Dの場合は
$ D = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2 + (z_1 - z_2)^2} $
となります。
以下、実例です。
$ b = 4, c = 2 $
$ a = \sqrt{4^2 + 2^2} = \sqrt{20} = 2\sqrt{5} $
$ (x, y) = (2, -2) $と$ (6, 1) $の距離$ D $
$ D = \sqrt{(2 - 6)^2 + (-2 - 1)^2} = \sqrt{16 + 9} = \sqrt{25} = 5 $
ABCでは、問題中で2点間の距離を求める必要が発生することがあります。
また、プログラム中でルートを計算すると誤差が発生してしまうため、あえてルートを計算せず、2乗した状態の数を持っておき、必要になったらルートをつけた数を求めるというテクニックも存在します。
最後に
ここまで読んでいただきありがとうございます。これらの知識はABCでは必須になるため、今回まとめてみました。もし内容に間違いがあった場合、速やかに修正させていただきます。
明日の記事はうえきさんです。どんな記事なのかな？