CodeChef - Expected Greatest Common Divisor

• 問題
• AC

答える数が特殊。$y=P \cdot Q^ {-1}$が$\mod 10^9 + 7$で求まっているとき、$N \equiv -y$である。

$\gcd$の期待値を求める問題だが、総和が求まればよい。

GCDごとに求める典型を思い出す。$f(X, r) := |\{(x_0, ..., x_{N-1}) \in X : \gcd(x_0, ..., x_{N-1}) = r\}|$とする時、求める総和は$\sum_r rf(X, r)$と表せる。最大公約数の代わりに公約数を考える: $F(X, r) := |\{(x_0, ..., x_{N-1}) \in X : r が x_0, ..., x_{N-1}の公約数\}|$。$r$ が $x_0, ..., x_{N-1}$の公約数であることは$x_0, ..., x_{N-1}$がすべて$r$の倍数であることと同値で、これは成分毎にわけて数えられる。つまり、$[A_i, B_i]$中の$r$の倍数の数が$\lfloor B_i / r \rfloor - \lfloor (A_i-1) / r \rfloor$で、$F(\prod_i [A_i, B_i], r) = \prod_i \bigl( \lfloor B_i / r \rfloor - \lfloor (A_i-1) / r \rfloor \bigr)$と計算できる。$F(X, r) = \sum_{r|m} f(X, m)$なので、$f$は$F$のメビウス変換で得られる。

全体の計算量は、$B= \max B_i$として${O}(BK + B\log\log B)$。$\lfloor A / r \rfloor$が高々${O}(\sqrt A)$種類の値しか取らないから、頑張れば${O}(K \sqrt B)$でできる？

ABC162 Eがこれの簡単バージョンだったことを思い出した。