\(C \neq 0\) である場合に \(C > 10^9\) が成り立つことを示します。

\(S=\lbrace \left. (\alpha,\beta) \right| \forall k \in [0,N), X_k=\lfloor \alpha k + \beta \rfloor \rbrace\) とします。 \((M,A,B)\) が条件を全て満たすことは \((A,B) \in MS\) が成り立つことと同値です。

また、 \((m,a,b)\) を条件を全て満たす辞書順で最小 \((K=1)\) の解とします。また、 \(\displaystyle \alpha_0 = \frac am,\ \beta_0 = \frac bm\) とします。

直線 \(y=\alpha_0 x + \beta_0 \) は上側に \(\displaystyle \frac1m\) 未満動かしても条件を満たします。これから、 \(\displaystyle \alpha \in \left[\alpha_0+\frac1{4m(N-1)} \right],\ \beta \in \left[\beta_0+\frac1{4m} \right]\) に対して必ず \((\alpha , \beta) \in S\) の成立が分かります。以降はこの長方形領域の中に含まれる解の個数を求めることを考えます。

\(L=2^{29}\) とし、 \(M\) の範囲を \(L\le M < 2L\) に絞って考えます。この範囲に解が \(10^9\) 個以上存在することを示せば良いです。

まず、 \(B\) の条件は \(\displaystyle \beta_0 \le \frac BM \le \beta_0 + \frac1{4m}\) です。したがって、\(M\) を固定した時に \(B\) は \(\displaystyle \left\lfloor \frac L{4m}\right\rfloor\) 個以上取ることができます。

また、 \(A\) の条件は \(\displaystyle \alpha_0 \le \frac AM \le \alpha_0 + \frac1{4m(N-1)}\) より \(\displaystyle \frac{aM}m \le A\le \frac{aM}m + \frac M{4m(N-1)}\) です。ここで、 \(\displaystyle S_0 = \left\lfloor \frac L{4(N-1)} \right\rfloor\) とすると、 \(\displaystyle \frac M{4m(N-1)} \left(\geq \frac L{4m(N-1)} \geq \frac{S_0}m \right)\) より \(A\) の範囲を \(\displaystyle \frac{aM}m \le A\le \frac{aM}m+ \frac {S_0}{m}\) に絞って考えて良いです。

この範囲で考えたとき、\(A\) が一つ以上取れる \(M\) の条件は \(aM \bmod m \in \lbrace 0\rbrace \cup \lbrace m-S_0,m-S_0+1,\ldots,m-1\rbrace\) と同値です。この合同式の周期を考えることで、 \(A\) を取れる \(M\) は最低でも \(\displaystyle C=\frac m{\gcd(a,m)}\) として \(\displaystyle \left\lfloor \frac LC\right\rfloor\left\lceil (S_0+1)\frac Cm\right\rceil > \frac{L-m}m(S_0+1)\) 個以上存在することが分かります。

以上を合わせると、 \(M < 2^{30}\) の範囲に解は最低でも \(\displaystyle \left\lfloor \frac L{4m} \right\rfloor \frac{L-m}m\left(\left\lfloor \frac L{4(N-1)} \right\rfloor +1\right)\) 個以上存在します。 \(m \le N-1\) と \(N \le 2\times 10^5, L = 2^{29}\) を用いるとこの値は \(1.2\times 10^9\) 以上であることが分かるので、\(M < 2^{30}\) を満たす解の個数が \(10^9\) 個以上あることが示されました。