ABC177_E – Coprime
問題
提出
解けた
以下、解法を書く。
setwiseに関しては、全ての$A_i$に対して順にgcdしていけば良い。
gcdの計算量は、2つの数を$a,b$とおくと、$\log(\min(a,b))$になる。
$A_i$全てに対する計算量を求めるにはどうしたらいいかわからないが、$O(N\log(\max(A_i)))$以上にはならないはず。
$N,A$の最大値は$10^6$なので、$10^6*\log(10^6)$程度の計算量になる。
pairwiseに関しては、全てのペアに対して計算すると$O(N^2)$になり、間に合わない。
「全てのペアで最大公約数が1」<=>「全ての$A_i$で素因数の重複がない」と考えてみる。
「全てのペアで最大公約数が1」=>「全ての$A_i$で素因数の重複がない」を証明してみる。
例えば$A_i$が3つの時
$\gcd(A_1,A_2)=1$かつ$\gcd(A_2,A_3)=1$かつ$\gcd(A_1,A_3)=1$である。
$\gcd(A_1,A_2)=1$なので、$A_1,A_2$間で素因数の重複はない。
$\gcd(A_2,A_3)=1$なので、$A_2,A_3$間で素因数の重複はない。
$\gcd(A_1,A_3)=1$なので、$A_1,A_3$間で素因数の重複はない。
よって、全ての$A_i$で素因数の重複はない。個数が3以上でも上記は成り立つので、「全てのペアで最大公約数が1」=>「全ての$A_i$で素因数の重複がない」である。
次に「全ての$A_i$で素因数の重複がない」=>「全てのペアで最大公約数が1」を証明してみる。
全ての$A_i$で素因数の重複がない時、素因数の重複がない数同士の最大公約数は$\gcd(A_i,A_j)=1$になる。
よって「全ての$A_i$で素因数の重複がない」=>「全てのペアで最大公約数が1」になる。
以上より、「全てのペアで最大公約数が1」<=>「全ての$A_i$で素因数の重複がない」と言い換え可能になる。
「全ての$A_i$で素因数の重複がない」かどうか調べる。
複数の数の素因数分解を高速にするには、エラトステネスの篩を使う。
計算の際にどの数に篩われたかを$f[x]$として覚えておく。
$f[x]$はxの約数のうち最小のものになっている。
$x=x/f[x]$として、繰り返し処理をすると、出現したxが素因数になっている。
エラトステネスの篩で$O(\max(A)\log\log(\max(A)))$になる。
$A_i$の素因数分解は最大で$O(log(A_i))$となるので、全ての素因数分解を行うと$O(\sum_{i=1}^N\log(A_i))$となる。
今回、$N,A$ともに最大値は$10^6$なので、素因数分解の計算量が大きく$10^6*\log(10^6)$程度の計算量になる。
コメント