391.1

もうちょっとでできそうと思っていたら、本当にできました、というお話。

1000

問題を再掲しておくと、long配列全体としての最小公倍数を維持したまま、先頭から順に可能な限り小さな約数に変えていくという問題。

今までに分かっていたことは、素因数分解をした上で、各素数を使用する回数が一番多いもののうち最後に出てくる数が、その素数について全責任を負い、他の数はその素数で割れるだけ割ってしまうということを行う。しかし全部の素数に対してやるのは効率が悪い。

これは実は1:1で計算すれば良くて、自分よりもある素数を多く使う(または同数で後続である)数が一つでも存在すれば、その素数で自分を割って良いということになる。2数間で最大公約数を求めると、すべての素数の共通使用回数が分かり、自分を最大公約数割ったときに、残りの素数が出てくる。この値の分については、他方の数ではなく、自分が責任を負う必要のあるものである。つまり、自分をこの数で割ってはいけない。自分が12で、最大公約数が6のときには、自分を2で割ってはいけないということになる。

で、実はこれらの値については計算を終了していたのだけれど、その後の処理を誤っていたのが一昨日の結果。二つの数の最大公約数をGとして自分をGで割った商をHとすると、Gを素因数分解したものが自分を割っていい可能性のある素数集合で、Hを素因数分解したものが自分を割ってはいけない素数集合である。また、後者の方が拘束力が強い。つまり素数集合のレベルで、G-Hをやる必要がある。もちろん素因数分解はする必要がなくて、コードで書くと以下のような感じになる。

while( gcd(G, H) > 1 ) {
  G /= gcd(G, H);
}

要はGとHとの公約数が、どちらにも現れる素数なので、それをGから除いていくだけ。後は1:1で全部の数について、G-Hを求めて割って行くというのをやれば良いだけ。コードにすると他の二問よりも短くなった。システムテストも通ったので大丈夫だろう。