https://www.codechef.com/problems/COOK82B
問題概要
N個の数列がある。
「A[i]の約数をkとするとき、A[i] = A[i] / k, A[j] = A[j] * kと変更する」操作をする。
この操作を行うことで数列を全て同じ要素にできるなら「justdoit」と出力。
もし、できない場合は、1つだけ要素をこの数列に追加してできるようにする。
追加する要素の最小値を答えよ。
前提知識
素因数分解 O(sqrt(N))
解法
https://www.codechef.com/viewsolution/13700350
今回の問題はテストケースからエスパーするのが取り組みとしていい。
なんで素因数分解してみるのって話だけれど、なんでだろうね。
4 = 2^2 6 = 2 * 3 14 = 2 * 7 9261 = 3^3 * 7^3 であり、これはならすと 42 = 2 * 3 * 7
約数で割って他に掛けるということは因数を渡している操作になっている。
全て同じ数にできるということは「全ての数をかけて素因数分解すると、各素因数の個数がNの倍数である」と言い換えられる。
そのため、justdoitかどうかはそれをやればいい。
そうでないなら、各素因数の個数がN+1の倍数になるように最小個数かけていけばいい。
1つ追加するのでN+1の倍数になっているのに注意
