三角形の中にある格子点の数は floor_sum で求めることができます。

これを用いると三角形の中にある格子点のうち \(x\) 座標が \(R\) 以下のものは何個ですか？という問題を座標の絶対値の最大値を \(M\) として \(O(\log{M})\) で解くことができます。

この問題の答えは単調増加であるため二分探索をすることで三角形の中にある格子点の \(x\) 座標の最小値が求まるので、その \(x\) 座標にある格子点をひとつ見つけて出力すれば良いです。

時間計算量は \(O(Q(\log{M})^{2})\) です。

実装例 c++