nashidos’s diary

アルゴリズムとか機械学習とか色々

競プロ・AtCoderで頻出の数学的知識まとめ

AtCoderのような競技プログラミングの世界では数学的知識が求められる問題が存在します。

本記事ではその中でも頻出の数学的知識とその知識を使って解ける問題を列挙しました。

Pythonでの実装例も合わせて載せています。

基数変換

基数変換とは「ある進数で表された進数を別の進数で表す」ことを言います。

例えば、10進数で表記された「3」を2進数に変換すると「11」になります。

基数変換を用いて解ける問題は以下の通りです。
B - Digits

基数変換のPythonコード

def Base_10_to_n(X, n):
    if (int(X/n)):
        return Base_10_to_n(int(X/n), n)+str(X%n)
    return str(X%n)

約数列挙

約数とは、「ある整数を割り切れる整数」のことを指します。

例えばある整数を「10」とすると、約数は「1, 2, 5, 10」になります。

約数列挙を用いて解ける問題は以下の通りです。
B - K-th Common Divisor

約数列挙のPythonコード

def make_divisors(n):
    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)
    # divisors.sort()
    return divisors

最大公約数

最大公約数とは、「2つ以上の正の整数に共通な約数(公約数)のうち最大のもの」を指します。

例えば「12」と「4」の場合、共通の約数として「2, 4」が挙げられます。すなわち、最大公約数は4になります。

最大公約数を用いて解ける問題は以下の通りです。
C - Sum of gcd of Tuples (Easy)

最大公約数を求めるPythonコード

import math
print(math.gcd(12, 4))
#出力 4

素数判定

素数とは「1と自分自身以外では割り切れない整数」を指します。

例えば「3」や「5」などは1と自分自身で割り切れないので素数となります。

反対に素数以外の整数を「合成数」と言ったりします(1は除く)。

素数判定を用いて解ける問題としては以下のようなものがあります。
A - 素数、コンテスト、素数
D - 2017-like Number

ちなみに素数判定には「エラトステネスの篩」という方法が使われることがあります。

少し難しい内容なので今回は触れませんが、別の記事で解説しています。
nashidos.hatenablog.com

素数判定のPythonコード

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

素因数分解

素因数分解とはある整数を「素数の積」の形で表現することを言います。

例えば24であれば 2^3 * 3^1と分解することができます。

素因数分解を用いて解ける問題は以下の通りです。
D - Disjoint Set of Common Divisors

素因数分解Pythonコード

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr