kanpurin https://blog.hatena.ne.jp/kanpurin/ かんプリンの学習記録 https://kanpurin.hatenablog.com/ ABC 典型 数え上げ 競技プログラミング 解説 数論 問題はこちら 問題概要 解説 提出プログラム 感想 問題概要整数が与えられるので，以下の条件を満たす整数組の数を求めよ． をの最大公約数とすると，以下が成立する． かつかつ 解説またはのときは条件を満たさないので，以下とする．各に対して，条件を満たすようなの数を求める．つまり，となるようなのうち，がともにより大きいの倍数かつであるようなものの数を求めたい． となるようなの数はとなる． ここで，はとなるなら，そうでないならとなる関数である．これは，による畳み込みとなっているので高速に求めることができる．この値からのどちらかがに等しいようなの数を引く．となるの数はとなるが，これも約数のゼータ変換を… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fkanpurin.hatenablog.com%2Fentry%2F2021%2F06%2F19%2F224001" title="ABC206 E - Divide Both - かんプリンの学習記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2021-06-19 22:40:01 rich https://kanpurin.hatenablog.com/entry/2021/06/19/224001 1.0 100%