はじめに
日常生活を送っていると、次のような問題を解きたくなるときがあります。
$Q$回のクエリが与えられる。
$i$個目のクエリでは、整数$a_i$の素因数分解したときの素因数をすべて出力せよ。
そういうときは、ないんじゃ！みたいな異論もあると思いますが、無いと思うのでないです（おい）
例えば、
3
10 4 20
の場合は
2 5
2 2
2 2 5
のようにそれぞれの素因数分解を行います。
肝心の制約は
- $Q{\leqq}10^5$
- $a_i{\leqq}10^6$
とします。
通常の素因数分解
通常一つの整数$x$の素因数分解は以下のようなコードで行います。
template<typename T>
vector<pair<T, T>> FACTORIZATION(T x) {
vector<pair<T, int>> ans;
for (T i = 2; i * i <= x; i++) {
if (x % i == 0) {
T count = 0;
while (x % i == 0) {
count++;
x /= i;
}
ans.push_back(make_pair(i, count));
}
}
if (x != 1) ans.push_back(make_pair(x, 1));
return ans;
}
$i=2$から整数$x$を割れるなら、割っていくことを考えます。
$i$が整数$x$を割り切れるとき、整数$i$は整数$x$の因数であることが分かります。
例えば、$x=15$は、$i=3$で割り切ることができるため、$i=3$は$x$の素因数となります。
ここで、割り切れることが出来るなら必ずその時の$i$は素数になっています。
なぜなら、小さい方から割れるだけ割っていけば$i$に関係する素数の要素はすべて消えて、異なる値の素数$i'$以外が残るためです。
この素因数分解は$O({\sqrt{x}})$で動作し、十分高速に動作します。
複数クエリに対する問題
今回の問題で、上記のFACTORIZAION関数は通用するでしょうか･･･？
残念ながら通りません。
今回クエリの数が$Q=10^5$、そして各整数は$10^6$です。
計算量は$10^5 {\times}{\sqrt{10^6}} = 10^8$となり、約$1$秒かかってしまいます。
また、除算は多く時間を要するため仮に通ったとしてもあまり嬉しい状況ではなく、本質的な解決に至っていはいません。
どうすればいいでしょうか？
Smallest Prime Factors
上記の問題に対処するアルゴリズムの前段階として、Smallest Prime Factorsという概念を考えます。
この言葉は適当なので、正しいのかはわかりません（おい）
Smallest Prime Factorsは、$1$から$N$までの各整数$x$の最小の素因数を$O(NlogN)$で求めるアルゴリズムです。
例えば、$N=10$ならば
| n | min_p |
|---|---|
| 2 | 2 |
| 3 | 3 |
| 4 | 2 |
| 5 | 5 |
| 6 | 2 |
| 7 | 7 |
| 8 | 2 |
| 9 | 3 |
| 10 | 2 |
のように各整数の最小の素因数を$O(NlogN)$で求めます。
これはエラトステネスの篩を応用したアルゴリズムになります。
template<typename T>
vector<T> smallest_prime_factors(T n) {
vector<T> spf(n + 1);
for (int i = 0; i <= n; i++) spf[i] = i;
for (T i = 2; i * i <= n; i++) {
// 素数だったら
if (spf[i] == i) {
for (T j = i * i; j <= n; j += i) {
// iを持つ整数かつまだ素数が決まっていないなら
if (spf[j] == j) {
spf[j] = i;
}
}
}
}
return spf;
}
int main() {
int N;
cin >> N;
auto spf = smallest_prime_factors(N);
for (int i = 0; i <= N; i++) {
cout << i << " " << spf[i] << endl;
}
return 0;
}
以上のような関数で求めることができます。
エラトステネスの篩は、$N$までの素数を$O(NlogN)$で求めることができます。
エラトステネスの篩も上記のようなコードを書きます。
今回のsmallest_prime_factorsと違う点としては、
- もし今の整数$i$が素数ならば
- 素数$i$を因数に持つ整数$j$を素数でないとチェックするのではなく、もしまだ最小の素数が決まってないなら、最小の素数は$i$と記憶する
という点です。
これによって、素早く$1$から$N$までの各整数の最小の素因数を求めることができました。
これが分かると、実はより高速に複数クエリの素因数分解に対応することができます。
複数クエリの素因数分解
複数クエリの素因数分解では、先程求めたspf配列を使います。
spf配列は$1$から$N$までの各整数の最小の素因数が入っています。
ここで、整数$x$の素因数分解をすることにしましょう。
整数$x$の素因数を一個言え！と言われたら何になるでしょうか･･･？
整数$x$の素因数すべてをズバリということは難しそうですが、先程求めたspf配列によって、最小の素因数pは分かりそうです。
よって、整数$x$は$x = y{\times}p$と素因数分解出来ることが分かりました。
ここで、まだ整数$y$が素数でない、複数の素数を因数に持つ可能性があります。
ここでまた、先程のspf配列を利用することで、$y$の最小の素因数$p'$を求めることができます。
これを$1$になるまで繰り返していくことで、あっと言う間に整数$x$の素因数分解を行うことができます。
どれくらいあっという間か？を考えています。
現在、考えている整数の大きさは最大$10^6$です。$10^6$が最大持てる素数の数はおおよそ$20$個です。($2^20$はだいたい$10^6$)
よって、たかだか最大でも$20$回ぐらいしか各クエリに対して計算をしないことになります。
よって、spf配列を$O(NlogN)$で求めておくことで、各クエリに対する素因数分解を$O(Qlogx_i)$で求めることができてうま味です。
template<typename T>
vector<T> smallest_prime_factors(T n) {
vector<T> spf(n + 1);
for (int i = 0; i <= n; i++) spf[i] = i;
for (T i = 2; i * i <= n; i++) {
// 素数だったら
if (spf[i] == i) {
for (T j = i * i; j <= n; j += i) {
// iを持つ整数かつまだ素数が決まっていないなら
if (spf[j] == j) {
spf[j] = i;
}
}
}
}
return spf;
}
template<typename T>
vector<T> factolization(T x, vector<T> &spf) {
vector<T> ret;
while (x != 1) {
ret.push_back(spf[x]);
x /= spf[x];
}
sort(ret.begin(), ret.end());
return ret;
}
int main() {
constexpr int MAX = 1000000;
auto spf = smallest_prime_factors(MAX);
int Q;
cin >> Q;
while (Q--) {
int x;
cin >> x;
auto result = factolization(x, spf);
for (auto z: result)cout << z << " ";
cout << endl;
}
return 0;
}
ついに計算量内で計算することができました！
最後に
今回は、複数のクエリの素因数分解を高速に処理する方法についてまとめました。
ただ、闇雲にこの方法を使うことはできません。
例えば、制約が
- $Q{\leqq}10$
- $a_i{\leqq}10^{12}$
のような場合を考えてみます。
このような時、以上の方法では、10^{12}だけのメモリ空間と計算量が必要となってしまうため、非現実的です。
このような場合は、各クエリごとに普通の素因数分解で殴ると良さそうです。
なにかわからないことやアドバイスをいただけると嬉しいです！
ガナリヤでした！
参考サイト
https://www.geeksforgeeks.org/least-prime-factor-of-numbers-till-n/
https://www.geeksforgeeks.org/prime-factorization-using-sieve-olog-n-multiple-queries/