コンテンツにスキップ

素因数分解

タグ「素因数分解」の記事 4 件

素因数分解のリンク集

素因数分解について、参考になる記事や資料をまとめました。

素因数分解は、正の整数を素数の積で表すことです。1 つの整数 NN なら、2,3,4,…2, 3, 4, \dots で順に割れるだけ割っていき、i2>Ni^2 > N になったところで止めて、残った数が 11 より大きければそれも素因数に加える「試し割り」で O(N)O(\sqrt{N}) です。MM 以下の整数をたくさん素因数分解するなら、エラトステネスの篩で各整数の最小素因数(SPF)を前計算しておくと、1 個あたり素因数の個数(O(log⁡M)O(\log M))回の割り算で済みます。NN が 101810^{18} 程度まで大きいときは、Miller-Rabin 法で素数判定をしながら Pollard’s rho 法で約数を探すと、およそ O(N1/4)O(N^{1/4}) で分解できると期待できます(厳密な解析は未解決です)。

試し割りのループの条件は、sqrt を使わずに i * i <= N と整数で比べると誤差の心配がありません。ただし NN が 2312^{31} を超えうるなら、i も 64 bit 整数にしないと i * i があふれます。Miller-Rabin 法や Pollard’s rho 法で 101810^{18} 程度の数を扱うときは、法 NN での掛け算の途中の値が 64 bit に収まらないので、128 bit 整数(__int128)やモンゴメリ乗算を使います。Miller-Rabin 法の底は、64 bit 整数なら最初の 12 個の素数 2,3,5,…,372, 3, 5, \dots, 37 を使えば必ず正しく判定できます。底を少なく済ませると、強擬素数を素数と誤判定することがあります。AtCoder Library(ACL)には素因数分解の関数はありません。

  • AtCoder 版!マスター・オブ・整数 (素因数分解編)(drken、Qiita)
    • 素数判定、約数列挙、素因数分解を、どれも N\sqrt{N} までの試し割りで行う方法を C++ のコードつきで説明しています。割れるだけ割ると、割り切れる数が必ず素数になる理由や、最後に残った数が素数になる理由も丁寧に書かれています。後半は、約数の個数・約数の総和・オイラー関数の求め方と、素因数分解を考察に使う AtCoder の問題の解説、問題集です。
  • Integer factorization(cp-algorithms、英語)
    • 前半は試し割りと、その高速化(2・3・5 の倍数を飛ばす wheel factorization、篩で求めた素数だけで割る方法)です。後半はフェルマー法、Pollard の p−1p - 1 法、Pollard’s rho 法(Floyd と Brent の循環検出)を C++ のコードつきで説明しています。
    • rho 法のコードは約数を 1 つ見つけるだけで、素数判定と組み合わせて再帰的に分解する部分はありません。フェルマー法のコードは int を使っていて、nn が 2312^{31} に近いと a*a があふれます。

エラトステネスの篩と最小素因数(SPF)

Section titled “エラトステネスの篩と最小素因数(SPF)”
  • エラトステネスの篩の活用法を総特集! 〜 高速素因数分解・メビウスの反転公式 〜(drken、Qiita)
    • 篩の仕組みと O(Nlog⁡log⁡N)O(N \log\log N) の計算量を説明したあと、篩のついでに各整数の最小の素因数 minfactor を記録し、NN 以下の整数を 1 個あたり O(log⁡N)O(\log N) で素因数分解する方法を C++ の構造体で示しています。続けて、約数列挙、メビウス関数、高速ゼータ変換・メビウス変換、添字 GCD 畳み込みまで扱っています。
    • minfactor を求める最初のコード片は、戻り値の型が vector<bool> なのに return がありません。そのあとの構造体版のコードを使ってください。また、約数の個数を σ(n)\sigma(n) と書いていますが、ふつう σ(n)\sigma(n) は約数の和を表します。
  • 高速素因数分解(osa_k、日記)
    • 篩で各整数の最小の素因数を記録しておき、それで割ることを繰り返して素因数分解する方法を紹介し、素数で順に割る方法と 10710^7・10810^8 までの全整数で速さを比べています。競プロではこの方法が「osa_k 法」と呼ばれることがあります。
    • 本文の試し割りの計算量の見積もり(O(N+ln⁡N)O(N + \ln N) など)は、N\sqrt{N} まで調べれば十分であることを考えていない粗いものです。
  • Linear Sieve(cp-algorithms、英語)
    • 各合成数をその最小の素因数で 1 回だけ消す線形篩で、最小の素因数の配列を O(n)O(n) で求めます。正当性の証明つきです。実際の速さはふつうのエラトステネスの篩と同じくらいで、メモリは多く使うことにも触れています。
  • Sieve of Eratosthenes(cp-algorithms、英語)
    • 篩の実装と計算量の証明、n\sqrt{n} までで止める・奇数だけを扱うといった高速化のあと、「Segmented Sieve」と「Find primes in range」の節で区間篩を説明しています。後者は、R\sqrt{R} 以下の素数で区間 [L,R][L, R] の中の倍数を消していく方法で、R≈1012R \approx 10^{12}、R−L+1≈107R - L + 1 \approx 10^7 の例が挙げられています。
    • 扱っているのは区間内の素数の列挙だけで、区間内の各整数を素因数分解する方法には触れていません。

大きな数の素因数分解(Miller-Rabin 法・Pollard’s rho 法)

Section titled “大きな数の素因数分解(Miller-Rabin 法・Pollard’s rho 法)”
  • 素因数分解の高速なアルゴリズム(ロー法)(高校数学の美しい物語)
    • ロー法の手順と、誕生日のパラドックスをもとに N1/4N^{1/4} 回程度の反復で約数が見つかると期待できる理由を説明しています。厳密な解析が未解決であることも明記しています。コードはありません。
  • Primality tests(cp-algorithms、英語)
    • 試し割り、フェルマーテスト、Miller-Rabin 法を説明し、64 bit 整数を確実に判定できる底(7 個の底 2,325,9375,…2, 325, 9375, \dots または最初の 12 個の素数)を使った、__uint128_t による C++ の実装を載せています。素因数分解に使うときは、上の「Integer factorization」の rho 法と組み合わせます。
    • 最初の試し割りのコードは int で d * d を計算しているので、xx が 2312^{31} に近い素数のときにあふれます。

Miller-Rabin 法や Pollard’s rho 法を扱う講座はまだありません。

  • 素数の性質
    • O(N)O(\sqrt{N}) の素数判定から始め、素因数分解の一意性を証明し、O(N)O(\sqrt{N}) の試し割りによる素因数分解を Python で示しています。pp 進付値 vp(N)v_p(N) と、約数・最大公約数・最小公倍数を指数で言い換える方法も扱っています。後半は有理数の合同式とフェルマーの小定理です。
  • 素数篩
    • エラトステネスの篩、最小素因数の配列、線形篩、区間篩を、擬似コードと証明つきで説明しています。最小素因数を使うと 1 個あたり素因数の個数の回数で素因数分解でき、11 から NN まで全部分解しても O(Nlog⁡log⁡N)O(N \log\log N) であることを示し、約数の個数・約数の和・オイラーの φ\varphi 関数の列挙にも応用しています。区間内の整数をまとめて素因数分解できることには一言触れていますが、詳細は省略されています。関連問題の一覧つきです。
  • 素数に関する評価
    • 素数の個数や素数の逆数和などの評価を証明する講座です。「4.5. 素因数の個数」の節で、相異なる素因数の個数 ω(N)\omega(N) が O(log⁡N/log⁡log⁡N)O(\log N / \log\log N) であることを示しています。
  • Prime Factor (素因数分解)(Luzhiled’s Library)
    • O(n)O(\sqrt{n}) の試し割りで、素因数と指数の map を返す短い実装です。
  • 高速素因数分解(Miller Rabin/Pollard’s Rho)(Nyaan’s Library)
    • Miller-Rabin 法と Pollard’s rho 法による素因数分解と、素因数ごとの個数の map、約数列挙の関数があります。ドキュメントは Miller-Rabin 法の説明だけで、rho 法の節は未執筆(TODO)です。
    • n>262n > 2^{62} のときは exit(1) で終了します。101810^{18} までなら問題ありません。
  • fast-prime-factorization.hpp(Luzhiled’s Library)
    • 同じく Miller-Rabin 法と Pollard’s rho 法による 64 bit 整数の素因数分解で、モンゴメリ乗算を使っています。ドキュメントはなく、コードだけです。
  • 素因数分解(日本語版 Wikipedia)
    • 定義と一意性、試し割りと、大きな数向けのアルゴリズム(ρ 法、楕円曲線法、数体篩法など)の名前の一覧、一般の環での素元分解、大きな数の分解の記録を扱っています。各アルゴリズムの説明はありません。
  • ポラード・ロー素因数分解法(日本語版 Wikipedia)
    • Floyd の循環検出による元のアルゴリズムと、Brent の変形の擬似コード、n=8051n = 8051 の分解例があります。
    • 概念の節で擬似乱数として「線形合同法など」を挙げていますが、一次式では誕生日のパラドックスによる速さが得られません。使用例の節にあるとおり f(x)=x2+cf(x) = x^2 + c を使ってください。
  • ミラー–ラビン素数判定法(日本語版 Wikipedia)
    • 判定の根拠になる「11 の平方根は ±1\pm 1 だけ」という補題、アルゴリズム、Ruby のコード、誤判定の確率が 4−k4^{-k} 以下であることを説明しています。
    • 決定的に判定できる底の表は n<341,550,071,728,321n < 341{,}550{,}071{,}728{,}321 までしかなく、64 bit 整数全体での底は載っていません。それは英語版を見てください。
  • Pollard’s rho algorithm(英語版 Wikipedia)
    • 考え方、擬似コード、n=8051n = 8051 と n=10403n = 10403 の分解例、Brent の変形と、gcd をまとめて計算する高速化、計算量の見積もりがあります。
  • Miller–Rabin primality test(英語版 Wikipedia)
    • 強擬素数の考え方と証明、アルゴリズム、精度の評価に加えて、「Testing against small sets of bases」の節に、nn の範囲ごとに十分な底の一覧があります。n<264n < 2^{64} なら 2,3,5,…,372, 3, 5, \dots, 37 の 12 個で十分であることも書かれています。
  • アルゴリズムと数学 演習問題集 014 - Factorization:N≤1012N \le 10^{12} を試し割りで素因数分解して出力する基本問題です。
  • ABC169 D - Div Game:N≤1012N \le 10^{12} を素因数分解し、素因数ごとに指数を 1,2,3,…1, 2, 3, \dots と小さい順に使っていきます。
  • ABC280 D - Factorial and Multiple:K≤1012K \le 10^{12} を素因数分解し、素因数 pep^e ごとに N!N! が pep^e で割り切れる最小の NN を求めます。
  • CADDi 2018 C - Product and GCD:PP を素因数分解し、各素因数の指数を NN 個に均等に分けます。
  • ABC110 D - Factorization:MM を素因数分解し、素因数ごとに指数を NN 個の項へ配る方法を重複組合せで数えます。
  • ABC052 C - Factors of Factorial:11 から NN までを素因数分解して N!N! の各素因数の指数を足し合わせ、約数の個数を求めます。
  • ABC177 E - Coprime:10610^6 個の整数を最小素因数の前計算で素因数分解し、同じ素因数が 2 回現れるかを調べます。
  • ABC342 D - Square Pair:各要素から平方数の因子を取り除いた値を素因数分解で求め、それが等しい組を数えます。00 の扱いに注意します。
  • ABC227 G - Divisors of Binomial Coefficient:N≤1012N \le 10^{12} に対し、区間 [N−K+1,N][N - K + 1, N] の整数を区間篩でまとめて素因数分解します。
  • ABC412 E - LCM Sequence:1,…,n1, \dots, n の最小公倍数が変わるのは nn が素数のべきのときなので、区間篩で区間内の素数のべきを数えます。
  • Library Checker - Factorize:101810^{18} 以下の整数を最大 100100 個素因数分解します。Pollard’s rho 法の verify 用です。
  • Library Checker - Primality Test:101810^{18} 以下の整数を最大 10510^5 個素数判定します。Miller-Rabin 法の verify 用です。
  • Blitz Round #25 C - Root Value
    • 各 ai≤200a_i \le 200 を 200200 以下の 4646 個の素数で試し割りし、素数ごとの指数の累積和から区間の積の指数を求めて、その最大公約数を答えています。
  • DOJ Beginner Contest 11 G - Déjà vu
    • 操作を素数ごとの指数で考えて、すべての要素で指数が等しい素数だけが f(b)f(b) に残ることを示し、f(b)=cf(b) = c となる部分列の個数を cc の大きい順に求めています。
  • ShareOJ Programming Contest vol.1 B - One Digit Factorization
    • 1 桁の整数の積で表せることを素因数が 2,3,5,72, 3, 5, 7 だけであることに言い換え、N≤1018N \le 10^{18} をそれらで割れるだけ割って 11 が残るかで判定しています。

ShareOJ Programming Contest vol.1 B - One Digit Factorization

正整数 NN が、11 桁の正整数だけの積で表せるかを判定する問題です。テストケースは TT 個あり、1≤T≤1001 \le T \le 100、1≤N≤10181 \le N \le 10^{18} です。

NN が 11 桁の正整数だけの積で表せることは、NN の素因数が 2,3,5,72, 3, 5, 7 だけであることと同じです。

  • 11 桁の正整数 1,2,…,91, 2, \dots, 9 は、どれも素因数が 2,3,5,72, 3, 5, 7 だけです。そのため、これらの積の素因数も 2,3,5,72, 3, 5, 7 だけです。
  • 逆に、素因数が 2,3,5,72, 3, 5, 7 だけなら、NN を素因数分解した式がそのまま 11 桁の正整数の積になっています。N=1N = 1 のときも、11 自体が 11 桁なので表せます。

NN を 2,3,5,72, 3, 5, 7 でそれぞれ割り切れなくなるまで割り、最後に 11 が残れば Yes、そうでなければ No です。

1 回割るたびに NN は半分以下になるので、割る回数は log⁡21018<60\log_2 10^{18} < 60 回ほどで済みます。

Python
for _ in range(int(input())):
N = int(input())
for p in [2, 3, 5, 7]:
while N % p == 0:
N //= p
if N == 1:
print("Yes")
else:
print("No")

DOJ Beginner Contest 11 G - Déjà vu

正の整数列 a=(a1,a2,…,aN)a = (a_1, a_2, \dots, a_N) が与えられます。空でない部分列 bb に対して、次の操作を何回でも行えます。

  • 素数 pp を 1 つ選び、bb の要素のうち pp で割り切れるものをすべて同時に pp で割る。

bb の要素をすべて同じ値にするとき、その値の最大値を f(b)f(b) とします。すべての空でない部分列 bb についての f(b)f(b) の和を 998244353998244353 で割った余りを求める問題です。

ai≤2×105a_i \le 2 \times 10^5 で、NN の総和は 5×1055 \times 10^5 以下、max⁡a\max a の総和は 2×1052 \times 10^5 以下です。

素数 pp ごとに考えます。bb の各要素を素因数分解したときの pp の指数を見ると、pp を選ぶ操作は、正の指数をすべて 11 ずつ減らし、00 の指数はそのままにします。

最後にすべての指数を e>0e > 0 でそろえるには、正の指数どうしの差は変わらず、00 の指数は増えないので、はじめからすべての指数が ee でなければなりません。そうでなければ、すべて 00 にそろえるしかありません。

よって、f(b)f(b) は「bb のすべての要素で指数が等しい素数」について pep^e を掛けたものです。ここから次のことがいえます。

  • bb のすべての要素が c⋅jc \cdot j(gcd⁡(c,j)=1\gcd(c, j) = 1)の形で書ける   ⟺  \iff cc を割り切るどの素数についても、bb のすべての要素の指数が cc の指数と等しい   ⟺  \iff f(b)=c⋅df(b) = c \cdot d(gcd⁡(c,d)=1\gcd(c, d) = 1)と書ける

f(b)=cf(b) = c となる部分列の個数

Section titled “f(b)=cf(b) = cf(b)=c となる部分列の個数”

aa の要素のうち、c⋅jc \cdot j(gcd⁡(c,j)=1\gcd(c, j) = 1)の形のものの個数を tct_c とします。これらだけからなる空でない部分列は 2tc−12^{t_c} - 1 個あり、上の性質から、これはちょうど f(b)=c⋅jf(b) = c \cdot j(gcd⁡(c,j)=1\gcd(c, j) = 1)となる部分列全体です。f(b)=cf(b) = c となる部分列の個数を gcg_c とすると、

gc=2tc−1−∑j≥2, gcd⁡(c,j)=1gcjg_c = 2^{t_c} - 1 - \sum_{j \ge 2,\ \gcd(c, j) = 1} g_{cj}

です。cc の大きい順に計算すれば、右辺の gcjg_{cj} はすでに求まっています。答えは ∑cc⋅gc\sum_c c \cdot g_c です。

M=max⁡aM = \max a とすると、cc ごとに M/cM / c 個の倍数を見るので、全体で O(Mlog⁡M)O(M \log M) 回の gcd⁡\gcd 計算です。

Python
from math import gcd
MOD = 998244353
for _ in range(int(input())):
N = int(input())
A = list(map(int, input().split()))
M = max(A)
tmp0 = [0] * (M + 1)
tmp1 = [0] * (M + 1)
for a in A:
tmp0[a] += 1
ans = 0
for i in reversed(range(1, M + 1)):
t = tmp0[i]
u = 0
for j in range(2, M // i + 1):
if gcd(i, j) != 1:
continue
t += tmp0[i * j]
u += tmp1[i * j]
v = (pow(2, t, MOD) - u - 1) % MOD
tmp1[i] = v
ans += i * v
ans %= MOD
print(ans)

tmp0[x] は値 xx の要素の個数、tmp1[c] は gcg_c です。t が tct_c、u が ∑gcj\sum g_{cj} にあたります。

Blitz Round #25 C - Root Value

正の整数 xx に対して、xm\sqrt[m]{x} が自然数になるような最大の mm を f(x)f(x) とします。

長さ nn の数列 a1,…,ana_1, \ldots, a_n (2≤ai≤2002 \le a_i \le 200) と qq 個のクエリ (l,r)(l, r) が与えられるので、各クエリについて

f(∏i=lrai)f\left(\prod_{i=l}^{r} a_i\right)

を求める問題です。

  • 1≤n,q≤2⋅1051 \le n, q \le 2 \cdot 10^5、テストケースの nn の総和と qq の総和はそれぞれ 2⋅1052 \cdot 10^5 以下

正確な問題文は元の問題ページを見てください。

xx を素因数分解して x=p1e1p2e2⋯pkekx = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} とすると、xm\sqrt[m]{x} が整数になるのは、すべての指数 eje_j が mm の倍数のときです。したがって

f(x)=gcd⁡(e1,e2,…,ek)f(x) = \gcd(e_1, e_2, \ldots, e_k)

です。ai≥2a_i \ge 2 なので、積は 22 以上になり、指数のどれかは正になります。

積をそのまま計算すると巨大になりますが、指数だけを見れば足し算になります。ai≤200a_i \le 200 なので、現れる素数は 200200 以下の 4646 個だけです。各素数について指数の累積和を持っておけば、区間 [l,r][l, r] での各素数の指数は差を取るだけで求まり、その gcd⁡\gcd が答えです。

aia_i の上限を AA (=200= 200)、AA 以下の素数の個数を π(A)\pi(A) (=46= 46) とすると、計算量は O((n+q) π(A))O((n + q)\,\pi(A)) です。

Python
from math import gcd
prime = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199]
for _ in range(int(input())):
N, Q = map(int, input().split())
A = list(map(int, input().split()))
acc = [[0] * len(prime)]
for a in A:
t = acc[-1].copy()
for i, p in enumerate(prime):
while a % p == 0:
t[i] += 1
a //= p
acc.append(t)
for _ in range(Q):
l, r = map(int, input().split())
l -= 1
ans = 0
for i in range(len(prime)):
ans = gcd(ans, acc[r][i] - acc[l][i])
print(ans)