読者です 読者をやめる 読者になる 読者になる

SRM425 Div2Easy - Inverse Factoring

問題概要
正の整数 n の "proper factor" とは、1 と n を含まない n の因数として定義づけられる。ある正の整数 n の全ての "proper factor" が int[] で入力されるので、ここから n を導け。

解法
入力の最小の要素と最大の要素の積が答えとなる。

以下 editorial を参考

n のある因数が f1 であるとき、f2 = n/f1 もまた n の因数である。よって n = f1 * f2 と表せる。
別の n の因数 a1 があり、a1 < f1 であるとする。このとき a2 = n/a1 もまた n の因数である。よって n = a1 * a2 である。n = f1 * f2 と a1 < f1 とから、f2 < a2 である。

つまり n を生成するには、prime factors の対称の位置にある値のペアのどれでもよいので、その積を取れば良いことになる。もっとも手軽なのか最小と最大の積。