線分上の格子点の個数
数学っぽい問題好き!!! 問題へのリンク editorials 問題概要 個のカフェオレがある。 番目のカフェオレは、コーヒーが mg、ミルクが mg だけ入っている (ともに整数)。 これらを混ぜて作れるカフェオレのうち、コーヒー量 とミルク量が がともに正の整数…
yukicoder
約数
約数系包除
高速ゼータ変換
累積和
数え上げ問題
高速メビウス変換
高速畳み込み計算
エラトステネスの篩
整数問題
線分上の格子点の個数
添字GCD畳み込み
最大公約数の値を固定して考える
メビウス関数
添字 GCD 畳み込みの練習に 問題へのリンク 問題概要 の格子点上の二点対であって、その二点を結ぶ線分上に格子点をもたないものが何個あるかを数え上げよ。(1000000007 で割ったあまりで) 制約 解法 1:添字 GCD 畳み込み この問題は、線分として 軸や 軸に…