かんプリンの学習記録

勉強したことについてメモしています. 主に競技プログラミングの問題の解説やってます.

ABC206 E - Divide Both

ABC 典型 数え上げ 競技プログラミング 解説 数論

問題はこちら

問題概要

整数{L,R(L\leq R)}が与えられるので，以下の条件を満たす整数組{(x,y)}の数を求めよ．

  • {L\leq x,y\leq R}
  • {g}を{x,y}の最大公約数とすると，以下が成立する．
    • {g\neq 1}かつ{\frac{x}{g}\neq 1}かつ{\frac{y}{g}\neq 1}

{1\leq L\leq R\leq 10^6}

解説

{x=1}または{y=1}のときは条件を満たさないので，以下{L\leftarrow\max(2,L)}とする．

各{g(2\leq g\leq R)}に対して，条件を満たすような{(x,y)}の数を求める．つまり，{\gcd(x,y)=g}となるような{(x,y)}のうち，{x,y}がともに{g}より大きい{g}の倍数かつであるようなものの数を求めたい．
{\gcd(x,y)=g}となるような{(x,y)}の数は{\displaystyle \sum_{g=2}^{R}\sum_{\gcd(x,y)=g}f(x)f(y)}となる．
ここで，{f(x)}は{L\leq x\leq R}となるなら{1}，そうでないなら{0}となる関数である．これは，{\gcd}による畳み込みとなっているので高速に求めることができる．

この値から{x,y}のどちらかが{g}に等しいような{(x,y)}の数を引く．{x=g}となる{(x,y)}の数は{\displaystyle\sum_{g=L}^{R}\sum_{g|y}f(y)}となるが，これも約数のゼータ変換を用いて高速に計算でき，対称性から{y}についても同じ値となる．ここから引きすぎた{\displaystyle\sum_{g=L}^{R}f(g)=R-L+1}を足せば答えとなる．

{\displaystyle \sum_{g=2}^{R}\sum_{\gcd(x,y)=g}f(x)f(y)-2\sum_{g=L}^{R}\sum_{g|y}f(y)+R-L+1}

以下の記事が参考になる．

{\gcd}による畳み込みやゼータ変換についての記事
qiita.com

提出プログラム

https://atcoder.jp/contests/abc206/submissions/23606820

感想

gcd畳み込みを使う問題たのしい．{g=R}となるようなことはないけど面倒なので入れた．