AtcorderABC-Dより先へ行くために代表的なアルゴリズムを勉強した-その2-（競プロにありがちな典型数学問題）

はじめに

• ABC-Dを解くために、競プロにありがちな典型数学問題を勉強しました。（C以下でも出ますが。）

手法

素数判定

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

is_prime(4)
# ->
# False

素因数分解

def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:   # iで割り切れれば、iはnの素因数
      n //= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(n)
  return table

A = 120
prime_decomposition(A)
# ->
# [2, 2, 2, 3, 5]

s = set(prime_decomposition(A))    #正整数Aの素因数のリストを集合に変換
# ->
# {2, 3, 5}

約数の列挙

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

make_divisors(12)
# ->
# [1, 12, 2, 6, 3, 4]

最大公約数

from fractions import gcd

a = 12
b = 18

max = gcd(a,b)
# ->
# 6

最小公倍数

from fractions import gcd

a = 12
b = 18

min = (a * b) // gcd(a,b)
# ->
# 36

二項係数

# 組み合わせ数を 1000000007 で割った余りを求める
# フェルマーの小定理
a = 5
b = 3

class ModComb:
    def __init__(self, MAX, mod=10 ** 9 + 7):
        fac = [1, 1]
        finv = [1, 1]
        inv = [0, 1]
        for i in range(2, MAX):
            fac.append(fac[i - 1] * i % mod)
            inv.append(mod - inv[mod % i] * (mod // i) % mod)
            finv.append(finv[i - 1] * inv[i] % mod)
        self.fac, self.finv, self.mod = fac, finv, mod

    def nCk(self, n, k):
        if n < k or n < 0 or k < 0:
            return 0
        fac, finv, mod = self.fac, self.finv, self.mod
        return fac[n] * (finv[k] * finv[n - k] % mod) % mod


mod = 10 ** 9 + 7
mc = ModComb(1000000, mod=mod) 

print(mc.nCk(a, b) % mod)