計算量と素因数分解
計算量、大事！
「ゆいちゃん、フレンドになろーー！！」
感心していると、ひまり先輩が突然部室に入ってきて抱き着いてきた！
「ゆいちゃん、PBCに参加してみた？」
「はい、面白かったです」
「初めてで四問はすごいじゃん！」
あの、ひまり先輩、もうちょっと力を緩めてもらえると助かります...ほら、哀先輩も苦笑いしてるし。
「じゃあ、今日は計算量の話をしようかな」
「PBCの5問目からは、計算量を意識しないと解けない問題が出るんだよね」
「計算量ってなんですか？」
「ざっくり言うなら、名前の通りプログラムが計算する回数だよ」
「実際に体験した方が早い」
「前回のPBCのE問題を見てみよー！」
E - Largest Prime Factor
実行制限時間:2sec/メモリ制限:1024MB
配点:250点
<<問題文>>
整数Nが与えられます。Nの素因数のうち、最も大きいものを出力してください。
<制約>
2 <= N <= 10^12
<入力形式>
N
<入力例1>
35
<出力例1>
7
<入力例2>
97
<出力例2>
97
えっと、問題文を読もう。Nが与えられるから、Nを素因数分解して、一番大きな素因数を答えればいいんだね。
例えば、入力例1は、35 = 5 * 7 だから、7を出力するんだね。
「ゆいちゃんにはこの問題に限らずまず考えてもらいたい解法があるんだけど、何だったかな？」
「「全探索」ですよね、最後に解いた問題で思い出したので解けました」
「お、偉いね！」
「何度も言うけど、競技プログラミングの基本は「全探索」だからね」
「じゃあ、この問題を全探索で解くプログラムを書いてみて！」
全探索ね......。中学校で習った素因数分解をするときみたいに、小さい数から割る数を全部試していけば解けそうかな。
こんなやつね。一番最後に出てくる素数がこの問題の答えになるね。
<<Python>>
N = int(input())
i = 2
while (i < N):
if N % i == 0:
N //= i
else:
i += 1
print(N)
入力例を試してみよう。
<<Terminal>>
>python main.py
>35
7
一つ目の入力例はあってる。
>python main.py
>97
97
うん。二つ目もあってる。よし、できた！
「できました」
「おー速いね」
「ゆいちゃんみたいな若い子が成長するのを見ると昔を思い出すのお、ふぉっふぉっふぉ」
「ひまちゃんはまだそんな年じゃないでしょ」
「じゃあ、「計算量」を実感してもらおうかな、パソコン借りるね」
<<Terminal>>
>python main.py
>998244353
あれ、答えが返ってこない...
「まあ、こんな感じだね」
「今書いたプログラムに998244353を入力すると、while文が何回実行されるか分かる？」
「998244353っていうのは、素数だっていうのが重要だね」
2から(998244353 - 1)までの数は全部素数の998244353を割れないから、Nは途中で小さくならないんだよね。だから、(998244353 - 1) - 2 + 1回かな。
「そうだね。そんな感じで、アルゴリズムがどれくらいの計算をするかを見積もったものを「計算量」っていうよ」
「このプログラムを例にして言うと、Nが入力されたとき、最悪ケース、つまりNが素数だった場合にだいたいN回の計算をすることが分かる。このことを、「最悪計算量がO(N)」と言う」
「今回の制約を見てみて」
<制約>
2 <= N <= 10^12
「時間内に実行できるプログラムの命令の数は10の7から8乗までって覚えておくといいよ」
「この問題ではNの上限が10の12乗で10の8乗より大きいから、O(N)のアルゴリズムでは制限時間に間に合わなさそうだということが分かる」
「つまり、実装する前から時間の見積もりができるのが嬉しいところだね」
へえ～。問題が難しくなってくると、そのプログラムの速度を考えないといけなくなってくるんだね。
「それじゃあ、全く別の方法を考えないといけないんですか？」
「いや、全然悪くない。このアルゴリズムはすぐに高速化できる」
「素数のときに最後まで調べてしまうことが問題だから、そこを直せばいいよ」
<<Python>>
N = int(input())
i = 2
# while文の条件を変えたよ！
while (i * i <= N):
if N % i == 0:
N //= i
else:
i += 1
print(N)
「実際に実行してみるね」
<<Terminal>>
>python main.py
>998244353
998244353
すごい、すぐに答えが返ってきた。
「ある数Nが素数であるかどうかって、実は最後まで調べなくても分かるんだよね」
「例えば、25が素数かどうかを調べるには、2から5までで十分だよ」
「え、全部調べなくていいんですか？」
「例えば、122を61で割ると、122 = 2 * 61 だから、その前に2で割れるよね」
「確かに」
「すこし変えただけだけど、このプログラムの最悪計算量はO(√N)になった」
「実は、一般的には素因数分解は難しい問題なんだよ」
「そうなんですか？中学校とかでやるから、簡単なんだと思ってました」
「ある数が素数であるか確かめるのが難しいことを利用したRSA暗号があるくらいだからね」
「今やったみたいに、計算量を減らして行ったら解けちゃったりしないんですか？」
「RSA暗号の鍵は4096bitくらいの数だから、全く心配いらない」
「今計算したのが64bitくらいだね」
「2^67 - 1の素因数分解をパソコンを使わずに解いてる人もいたけどね...さすがにこれくらいが人間の限界だと思うよ」
「2の67乗引く1ってどのくらいの数なんですか？」
「ちょっと計算してみようか」
<<Python>>
print(2**67 - 1)
<<Terminal>>
>python main.py
147573952589676412927
「本当にこれを手計算で因数分解したんですか...」
「さすがに真似できないね」
