77回生 PCT
こんにちは。中学3年生のPCTです。もう中学最終学年ということに驚いています。来年以降留年しないようにしたいですね。
趣味として、競技プログラミングと数学をしています。
今日はそんな趣味の1個、競技プログラミングのうち "数学問" と呼ばれるジャンルを少し説明しようと思います。
そもそも競技プログラミングって何？という方はWikipediaの「競技プログラミング」のページをご覧ください。
以下、\( 10^7 \) 回以下の計算で解を出すことを目標にします。
数学問というのは、例えば以下のような問題のことを言います。
正整数 \( N \) が与えられます。\( N \) の約数の個数を求めてください。
例えば、\( 1 \) 以上 \( N \) 以下の整数全てで割って割り切れるかを確かめる、という方法で \( N \) 回の計算で解を求められます。
この場合、制約1では間に合いますが、制約2だと計算するのに莫大な時間がかかってしまいます。
ここで、ある正整数 \( a \) が \( N \) の約数の時、\( \frac{N}{a} \) も \( N \) の約数であるということに注目します。
すると、\( \sqrt{N} \) から\( N \) まで探索しているのはとても効率が悪いです。
なので、\( 1 \) 以上 \( \sqrt{N} \) 未満を探索しながら、もし約数 \( b \) が見つかったとしたら \( \frac{N}{b} \) もカウントすることにします。この場合、\( \sqrt{N} \) が約数になることもあるのでその分のカウント忘れ、ダブルカウントに気を付けてください。
すると、この問題を \( \sqrt{N} \) 回の計算で解を求められ、制約2でも解くことができました。
ちなみに、\( \sqrt[4]{N} \) 回ほどの計算で正整数を素因数分解することができ、それを使うとこの問題はより高速に解けるのですが、その方法はとても難しいため今回は触れないことにします。
また、他にこのような問題もあります。
正整数 \( N \) が与えられます。\( N \) の約数の個数を求めてください。この問題は \( Q \) ケース与えられます。
上で言った通り、この問題は高速素因数分解(ポラード・ロー法と言われています。)で解くことができるのですが、今回はそれを使わないで解いてみます。
まず考えられる解法は、\( 2 \) 以上 \( N \) 以下の正整数について順番に割れるか試すという解法です。この解法はそれぞれ最高で \( \log{N} \) 回割り切れるので全体として \( N \log{N} \) に比例する回数の計算を必要とします。これで制約1について解くことができました。
また、制約1の解法を少し変えるだけで制約2も解くことができます。
なぜなら、\( N \) の素因数は \( 2 \) 以上 \( \sqrt{N} \) 以下であるか、\( N \) 自身であるかのどちらかのみなので上で\( 2 \) 以上 \( N \) 以下の正整数について処理しているところを \( 2 \) 以上 \( \sqrt{N} \) 以下の正整数について処理すればいいです。
よって、この解法で制約1,2を解くことができました。
しかし、この方法を \( Q \) 回繰り返していては制約3は間に合いません。
テストケース方式であることを利用して、前準備をしてから全テストケースに対して答えることを考えます。
どのような前準備をするのかというと、それぞれの正整数について約数のうち \( 2 \) 以上かつ最小のものを保持しておきます。
これは以下のようにすることで実行可能です。ここで、\( N \) の最大値を \( A \) とします。
この解法の計算量は、もし全ての要素について \( 0 \) ならば \( i \times j \) 番目の要素の内 \( 0 \) のものを \( i \) に変更することを繰り返す。 を実行したとしても計算量は調和級数の形になり \( \mathrm{O}(A \log A) \) で計算が完了します。実際は \( \mathrm{O}(A \log \log A) \) という計算量評価ができます。
次に、この情報を用いてある正整数 \( X \) を素因数分解します。
これで素因数分解を \( \mathrm{O}(\log X) \) ですることができました。
素因数分解の結果を用いて約数の個数を求めることは、それぞれの素因数の指数 \( +1 \) の積を求めることで実行可能です。
より、制約3でも解くことができました。
次に、以下の問題を考えます。
正整数 \( A,B \) が与えられます。\( X+Y=A,X^2+Y^2=B \) を満たす正整数の組 \( X,Y \) を求めてください。ただし、そのような正整数の組が存在しないならばそのことを報告してください。
制約：\( 1 \leqq A,B \leqq 10^{18} \)
愚直に \( X,Y \) のペアを全探索すると、\( 10^{36} \) 通りの候補を試すことになり間に合いません。また、\( X+Y=A \) という条件上で探索しても \( 10^{18} \) 通りの候補を試すこととなりこれもまた間に合いません。なので、以下のように直接 \( X,Y \) を求めることにします。
まず、\( \frac{A^2-B}{2}=XY \) を求めます。この値を \( C \) と置きます。もし \( C \) が整数にならないならばこの時点で条件を満たす正整数の組は存在しないことが分かります。次に、\( X,Y \) は \( p^2-Ap+C=0 \) の解となります。後はこの解を解の公式を使って計算すればよいです。ここで解が非負になったり、整数でなかったりする場合も条件を満たす正整数の組は存在しないことがわかります。
よってこの問題も解くことができました。\( 2 \) 次方程式に帰着する部分が少し難しいと思います。
では、最後の問題を紹介します。この問題はとても難しいと思います。ちなみにこの問題の製作者は私です。
以下の問題を \( T \) 回解いてください。
正整数 \( v,x \) が与えられます。ただし、\( xv+1 \) が素数であることが保証されています。以下の条件をみたす正整数列 \( a_1,a_2, \ldots ,a_x \) を \( 1 \) 個求めてください。
解が必ず存在することが保証されます。
制約
例えば、\( x=2,v=1 \) の時は \( a_1=1,a_2=2 \) が条件を満たします。なぜならば \( a_1^1+a_2^1=3 \) は \( xv+1=3 \) で割り切れ、\( a_1^2+a_2^2=5 \) は \( xv+1=3 \) で割って \( x=2 \) 余るからです。
この問題の解説は難しいので割愛します。ヒントは原子根です。
このページ にてジャッジが公開されているので、ぜひ挑戦してみてください。解説も載っています。
ここまで読んでいただきありがとうございました！