約数・倍数
1. 整数$ Nの約数の個数
$ Nを素因数分解して$ N=p_1^{e1}\cdot p_2^{e_2}\cdots p_m^{e_m}となったとき，約数の個数は$ (e_1+1)(e_2+1)\cdots (e_m+1)
計算量は，素因数分解の$ O(\sqrt N)
2. 1～$ Nまでの$ N個の整数に対する約数の個数
(1) 各整数の約数の個数を求める方法
各整数で$ O(\sqrt N)なので，全体で$ O(N\sqrt N)
(2) 最小素因数$ lpfを利用する方法
整数$ nの約数の個数を$ d(n)とし，$ i =1,\dots,n-1に対する$ d(i)と$ lpf(n)が算出済みとする．$ nを$ lpf(n)で最大$ k回割れるとすると，$ n = lpf(n)^k mと書ける．ここで，$ lpf(n) < mとなる点に注意．このとき，$ n > 1に対して，$ dp(n) = (k + 1)dp(m)が成立する．$ dp(1)=1とする．
数値例
$ n=1のとき，定義から$ d(1)=1
$ n=2のとき，$ lpf(2)=2．$ 2=2^1\times 1より，$ (k, m)=(1, 1)．よって，$ d(2)=(1+1)\cdot 1=2
$ n=3のとき，$ lpf(3)=3．$ 3=3^1\times 1より，$ (k, m)=(1, 1)．よって，$ d(3)=(1+1)\cdot 1=2
$ n=4のとき，$ lpf(4)=2．$ 4=2^2\times 1より，$ (k, m)=(2, 1)．よって，$ d(4)=(2+1)\cdot 1=3
$ n=5のとき，$ lpf(5)=5．$ 5=5^1\times 1より，$ (k, m)=(1, 1)．よって，$ d(5)=(1+1)\cdot 1=2
$ n=6のとき，$ lpf(6)=2．$ 6=2^1\times 3より，$ (k, m)=(1, 3)．よって，$ d(6)=(1+1)\cdot 2=4
$ n=7のとき，$ lpf(7)=7．$ 7=7^1\times 1より，$ (k, m)=(1, 1)．よって，$ d(7)=(1+1)\cdot 1=2
$ n=8のとき，$ lpf(8)=2．$ 8=2^3\times 1より，$ (k, m)=(3, 1)．よって，$ d(8)=(3+1)\cdot 1=4
$ n=9のとき，$ lpf(9)=3．$ 9=3^2\times 1より，$ (k, m)=(2, 1)．よって，$ d(9)=(2+1)\cdot 1=3
$ n=10のとき，$ lpf(10)=2．$ 10=2^1\times 5より，$ (k, m)=(1, 5)．よって，$ d(10)=(1+1)\cdot 2=4
code: python
# ### Nまでの約数の個数リストの作成 ###
def count_divisors(n: int) -> list:
is_prime = True * (n + 1) # is_primen：nが素数なら1，そうでないなら0．初期値は1 is_prime0 = is_prime1 = False lpf = list(range(n + 1))
d = 1 * (n + 1) # dn: nの約数の個数．d1 = 1で初期化 m = 2
while m * m <= n:
for km in range(m * m, n + 1, m):
m += 1
for m in range(2, n + 1):
while True:
if mm % p > 0:
break
mm //= p
cnt += 1
return d
# 使用例
print(count_divisors(100)) # [1, 1, 2, 2, 3, 2, 4, 2, 4, 3, 4,
3. 1つの整数$ Nの約数リストの作成
$ \sqrt{N}までの数で割れるかチェック．$ O(\sqrt N)
code: python
def make_divisors(n: int) -> list:
lower_divisors, upper_divisors = [], []
i = 1
while i * i <= n:
if n % i == 0:
lower_divisors.append(i)
if i * i < n:
upper_divisors.append(n // i)
i += 1
return lower_divisors + upper_divisors::-1 # 使用例
4. ルジャンドルの定理
Nの階乗 $ N!を素数 $ pで割り続けるとき，何回割れるか？
5. 最大公約数
math.gcd(x, y)
Python 3.9以降なら，math.gcd(x1, x2, x3)のように 3個以上も可能
ユークリッドの互除法で求められるが，最大公約数を求めるだけなら，上の関数で十分
6. 最小公倍数
Python 3.8以前では，(x * y) // math.gcd(x, y)
Python 3.9以降なら，math.lcm(x1, x2, x3)のように，3個以上も可能．