競プロで役に立ちそうな数学の知識 - ふたごはたいてい区別がつかない

はい、こんにちは.女の子と一緒にごはんにいって、少しでもいいから楽しいひと時を過ごしたい日々です.
近頃の現代数学的な内容から離れ、初等的な数学の中でも、きっと（おそらく）競プロで役に立ちそうな数学的知識を羅列したいと思います.*1

必要条件を使いこなす
初等整数論に慣れ親しむ

まだまだ書きたりてないので、初等整数論の部分は後日もっと書いて別記事でupします.

必要条件を使いこなす

数学の中でもっとも重要な概念のひとつが、必要条件と十分条件である.その中でも特に競プロで使いこなさなくてはいけないのは必要条件であろう.
重要性は必要条件がいかなるものかを理解すれば自ずと理解できる.実用的な用い方を言えば、考えるべき量をぐっと狭める手段である.
たとえば、 $n>5$ の整数が素数である必要条件は整数 $k \geq 1$ を用いて $n=6k-1$ または $n=6k+1$ と表せることである.
なぜなら、 $n=6k$ ならnは６の倍数であり、 $n=6k \pm 2$ なら2の倍数であり、 $n=6k \pm 3$ なら3の倍数である.以上より、素数であるならば $n=6k-1$ または $n=6k+1$ の形である.*2

上の例でみたように、必要条件で絞り込めば計算コストを大きく下げることができる.*3

初等整数論に慣れ親しむ

Die Mathematik ist die Königin der Wissenschaften und die Zahlentheorie ist die Königin der Mathematik. [Johann Carl Friedrich Gauß]*4

初等整数論とは、簡単に言えば中高程度の知識を用いる整数論のことである. 中高程度の知識とは言えども、整数問題は難易度が高く、簡単そうに見えても未解決問題だったりすることもある. たとえば有名なFermatの最終定理は、3以上の自然数nについて、xⁿ+yⁿ = zⁿをみたす自然数の組 $(x,y,z)$ は存在しない.という主張であるが、つい20年ほど前まで未解決問題であった. ただし、n=4の場合は大学入試にだせば易しいくらいの問題に変わる.*5

以下に知っておくべき初等整数論の知識の一部を紹介する.
Euclidの互除法
Euclidの互除法を用いて問題を解くことはできても、Euclidの互除法の定理の主張を言えない中高生は多いと思う.問題を解くことに熱意が注がれすぎる教育の悪いところである.
Euclidの互除法の主張は以下のようである. 整数 $a,b$ の最大公約数を $gcd(a,b)$ と表すことにする.
整数 $a,b$ に対し、aをbで割ったあまりをrとする.すなわち、 $a = qb+r$ $(0 \leq r \leq b-1)$ としたとき、 $gcd(a,b)=gcd(b,r)$ が成立する.
これをPythonで書けば以下のようになる.

def gcd(a,b):
    if b == 0:
        return a
    return gcd(b,a%b)

言葉の定義をしておこう.
素数素数とは、1とその数自身しか約数を持たない数のことである.
なにを当たり前なことをいっているんだと思われるかもしれないが、定義もしっかり言えないのに実用しようなんて無理なので念のため主張を書いておいた.

エラトステネスのふるい
エラトステネスのふるいというアルゴリズムをご存知だろうか.*6
具体例を通して考えてみよう.1~100までの自然数の中にある素数を全て列挙したい、どのようにして求めよう.
さて、上の項で素数とはいかなる数かを定義した.その定義にしたがってこの問題を考えるならば、1~100までの数字全てに対して約数を調べる方法を思いつくであろう.ただ、その方法は速いであろうか.100程度であればコンピューターを使わずとも手計算でもすぐ求まるであろう.しかし1億までの素数を全て列挙せよと言われたときにこの方法だと計算量が多すぎる.*7

この問いに対するエラトステネスのふるいの回答は、
2,3,5,7を除く2,3,5,7のいずれかで割り切れる数字を全て削除し、残ったものが素数である.

なぜ2,3,5,7で割り切れるかどうかを調べるだけで十分なのであろうか.これを説明するために以下の補題を解説する.

約数の性質
補題与えられた自然数Nの全ての約数を列挙したいとき、 $\sqrt{N}$ までの約数を求めれば十分である.
どういう主張かというと、例えば12の約数は1,2,3,4,6,12だが、前半の1,2,3さえ求めれば後半の4,6,12は自然に求めることができるといいう主張だ.
なぜこのようなことが言えるかと言えば、Nの約数は必ず掛け合わせたらNになる組を作ることができいるからだ.上の例で言えば、1に対して12、2に対して6、3に対して4といった具合である.

上の補題からわかることとして、以下のことがある.
約数の個数が奇数個である数は平方数である.
これは各自確かめて欲しい.

上の知識を使って、約数を列挙してみよう.Pythonで書けば以下のようになる.

N = int(input())
divisors = []
for i in range(1,int(N**0.5)+1):
    if N % i == 0:
        divisors.append(i)
        if i != N//i:
           divisors.append(N//i)