まず$( x _ 1, y _ 1 ) = (1, 0), \ (x _ 2, y _ 2 ) = ( 0, 1 )$ になるように $\mathbb Q$ 係数で線形変換しておきましょう。さらに同時に変換した $( x _ 3, y _ 3 )$ の分母を払い、

$$\left( \begin{array}{c} x _ 3 \\ y _ 3 \end{array} \right) = \frac 1 r \left( \begin{array}{c} a \\ b \end{array} \right)$$

（ただし $r \in \mathbb Z _ { \ge 0 }, \ a, b \in \mathbb Z$、$a$ と $b$ は互いに素）と表しておきます。

さて $x _ 1, x _ 2, x _ 3$ の適切な線型結合の個数を数えたいわけですが、$x _ 3$ の係数で場合分けします。重複を無視すると三角数になりますから、ここから重複を除いていきましょう。$x _ 3$ の係数の昇順で見て、今までに見た点と重複するものは数えないようにしましょう。重複は $r$ 個前のものとの重複だけを考えればよいです。（それより前のものとの重なりはこれに包含されます。）さらにこの重なりは三角数になります。

以上より $x _ 3$ の係数を固定するごとに三角数の差が足されることになるのですが、これを具体的に計算すると三角数の累積和 $3$ つの足し引きで表せます。三角数 $\binom n 2$ の累積和は $\binom n 3$ ですから、定数時間で求めることができます。