2020年3月26日数学約数,素因数分解,約数の個数

素因数分解を用いることで、約数の個数を簡単に求めることができます。

アルゴリズム

Nの約数の個数:

N を素因数分解する
それぞれの指数に1を足す
「2.」で得られたものを全てかけ合わせる

2020年3月23日AtCoder二項係数,Lucasの定理,偶奇性,パスカルの三角形,差の絶対値

問題へのリンク

問題概要

1,2,3 で構成された整数列 \(a_1 a_2 a_3 \cdots a_N\) が与えられ、\(x_{i,j}\) を以下のように再帰的に定義する。

\(x_{1,j} := a_j\) ...

2020年3月23日グラフグラフ,貪欲法,最小全域木,プリム法

無向グラフ \(G=(V,E)\) について、\(G\) の部分グラフ \(T\) が以下を満たす時、\(T\) は全域木(Spanning Tree) と言います。

\(T\) は木
\(T\) では\(V\) の任意の ...

2020年3月23日グラフグラフ,貪欲法,クラスカル法,最小全域木

無向グラフ \(G=(V,E)\) について、\(G\) の部分グラフ \(T\) が以下を満たす時、\(T\) は全域木(Spanning Tree) と言います。

\(T\) は木
\(T\) では\(V\) の任意の ...

2020年3月23日数学二項係数,動的計画法,パスカルの三角形

以下のような「上の2つを足して下の数字をつくる三角形」をパスカルの三角形といい、上から \(n\) 行目・左から \(k\) 個目の数は、\(_{n}\mathrm{C}_{k}\) に対応しています。(0-indexed)

2020年3月22日数学剰余,二項係数,Lucasの定理,素数の剰余,偶奇性

Lucasの定理を利用することで、二項係数(nCk) が偶数なのか奇数なのかを効率よく判定することができます。

アルゴリズム

Lucasの定理をそのまま利用したアルゴリズム:

\({}_{n_i}\mathrm ...

2020年3月22日数学剰余,二項係数,動的計画法,Lucasの定理,素数の剰余

Lucas の定理を利用すると、\(_{n}\mathrm{C}_{k}\)% \(p\) が \(O( p^2 \log_p n)\) で計算できます。素数 \(p\) が小さい場合は十分高速です。

Lucas の定理

任 ...

2020年3月21日数学最大公約数,配列,結合則

配列 A が与えられて、その全ての要素の最大公約数(GCD)を求めることを考えます。2つの最大公約数だけではなく、N個の要素の最大公約数を求めます。

例:

Input: A = {36, 12, 48}

2020年3月21日数学最大公約数,ユークリッドの互除法,拡張ユークリッドの互除法,1次方程式

最大公約数を求める高速なアルゴリズムとしてユークリッドの互除法が知られています。このユークリッドの互除法を拡張することにより、

$$ ax+by=gcd(a,b)$$

の形をした、2変数の一次方程式の整数解を求 ...

2020年3月20日数学最小公倍数,配列,結合則

配列 a の全ての要素の最小公倍数(LCM: least common multiple) を求めるアルゴリズムについてです。2つの最小公倍数だけではなく、N個の要素の最小公倍数を求めます。

Input: a = {1, ...