hitoare日記

たまに書きます

E - Coprime(AtCoder Beginner Contest 177)

問題リンク

atcoder.jp


問題概要

 N個の自然数からなる集合\( \{A_i \}\)が与えられる。

この集合が「pairwise coprime」「setwise coprime」「そのどちらでもない」のどれかを判定せよ。

ただし、「pairwise coprime」とは、どの相異なる2要素もそのGCDが1であることであり、「setwise coprime」とは、pairwise coprimeでなく、全ての要素のGCDが1であることを指す。

解法

まず、\(1 \leq A_i \leq 10^6\)なので、\(10^6\)以下の整数を高速に素因数分解できるようにエラトステネスの篩の要領で素因数のテーブルを作っておく。 

自然数A,Bに対し、AとBのGCDが1であるとは、AとBが同じ素因数を持たないことと同値である。

よって、pairwise coprimeかどうかを判定するには、\(A_1\)から順番に素因数を保存しながら「\(A_k\)の素因数のうち\( A_1,...,A_{k - 1} \)までに出てきたものが存在するか」をチェックすればよい。

また、setwise coprimeであることと「\(A_1,...,A_N\)全てに共通する素因数が存在しない」ことは同値である。

よって、素数pに対し\(f(p)\)を\(A_1,...,A_N\)の素因数に出てきた回数として、\(f(p)=N\)であるものが1つでも存在するかどうかをチェックすれば良く、存在しなければsetwise coprimeである。

(追記:本番は上の方針を取ったが、実際は全体のGCDを取るだけでいい。)

提出

https://atcoder.jp/contests/abc177/submissions/16325578

感想

かなり数学よりだと思ったけど意外とAC数が多い。