Educational Codeforces Round 16: D - Two Arithmetic Progressions

問題ページ

問題概要

2 つの等差数列の共通部分のうち、L以上R以下であるような項は何個あるか。

解法

等差数列の共通部分もまた等差数列になり、その公差は $T=\mathrm{lcm}(a_1, a_2)$ である。

初項を求めるために不定方程式 $a_1 k+b_1=a_2 l+b_2$ の特殊解を拡張ユークリッド互除法で求める。

特殊解から初項の mod T の値がわかるので、その値を使って $k\le 0, l\le 0$ になるものを二分探索で求める。オーバーフローを気にせず豪快に二分探索を掛けたいので python で書いた。

共通部分の初項と公差が分かれば後は簡単。

本番無駄に複雑な方法で初項を求めてしまった。計算するのが面倒なときは python で豪快二分探索を書くのが楽。