【C#】AtCoder Beginner Contest 142 D問題の素因数分解の処理について
ABC142 D問題でTLEになってしまい、終了後に解説をみていたのですが素因数分解の処理部分が最初はどうしても理解ができなかったのですが、色々と考えて自分で腹落ちさせたので残してみます。
問題の概要
詳細は問題文を参照。
解法
与えられた整数A、BのGCDを求めてそのGCDを素因数分解します。素因子の数＋１をしてあげれば答えになります。
ハマったポイント
A,BのGCDをNとした時、このNを素因数分解するには1からNまでの範囲にある素数で割って最後にNを割った商が素数になるまで計算していけば問題ありません。ただ、Nが非常に大きい数字の場合、今回の問題ではTLEになってしまう可能性があるので計算量を減らす必要があります。今回はこの計算量の削減ができなくてACまで持っていけませんでした。
ちなみに、この計算量を√Nにすることができます。この√Nで計算する時の処理がふわっとしていたので整理したいと思います。
試し割り法
素数かどうかを判定する(割り切れる数がないことを調べる)時に使う方法ですが、今回は”割り切れる数”を探していきます。特に大事なのは、Nという値の約数を確認するときは、√Nまでの値を確認すればよい、という点です。
例として、140という値で確認してみましょう。
このようになります。今回は素因子を数えるので、10までに登場する素数を対象として数えればOKです(2,5,7)。ただ、Nの素因子が√Nを超える場合が存在します。N=93という値で確認してみましょう。
このように、素数x素数が成立するパターンは√Nまでの計算では今回の問題は解決できません。(Nの素因子を数える場合、√N以降の素数も対象となるため。ただ、プログラムを愚直に書くとこのケースでは正しく素因子が数えられない。) そのため、プログラムでは√Nまで素因子の数を数え(素因数分解して)、一通り計算し終わったあとに"素因数分解"を確認します。1になっていなかった場合は素因子の数に＋１をします。ちょっと説明がややこしいのでコードを載せます。
long N = CalcGCD(A, B); double sqrt = Math.Sqrt(N); long count = 1; long n = 2; bool isFirst = true; while (n <= sqrt) { if (N % n == 0) { N /= n; if (isFirst) { count++; isFirst = false; } } else { isFirst = true; n++; } } if (N != 1) count++; Console.WriteLine(count);
入力ABの最大公約数Nを求め、素因数分解をしています。Nの平方根sqrtをもとめ、sqrtまでの値で素因数分解をしています。ただ、先程書いた素因子が√Nを超える場合について”if (N != 1) count++;”で処理をしています。
コード全体
これのD.csです。
