ABC177 - EをRubyで解く - Qiita

制約より、$2≤N≤10^6$ なので最大が $O(10^{12})$ となって実行時間制限2secに間に合わない。 ここでいずれの組み合わせの最大公約数が1となる点に注目する。 これはどの整数の組み合わせ $(A_i, A_j)$ も互いに素であると言い換えられる。 よって、N個の整数全てを素因数分解をして、同じ素因数が出てこなければこれが成り立ち、pairwise coprimeを出力する。 2.『GCD(A_1 …… A_N) = 1』が成り立つ これは愚直にまわしてもO(N)なので、考察する余地はない。 1が成り立たないとき、かつ、res == 1のとき、setwise coprimeを出力すればいい。 そして、3.いずれも成り立たないとき、not coprimeを出力する。 これより、1が考察の主となる。 素因数分解 Rubyにはprimeモジュールがあり、これのPrime.pr