Consider \(N\) lines \(A_ix+B_iy=C_i\) \((1\le i\le N)\). The problem asks to count lattice points with positive \(x\) and \(y\) coordinates under all the lines. For simplicity, we assume that no lines have the same slope, picking the lowermost one among those with the same slope.

For any line, the \(x\) coordinates for which that line is the lowermost line among the \(N\) lines form a segment. Finding the segment where each line exists at the lowermost is a dual of the convex hull problem, which can be solved in the same manner of convex hull algorithm by the following steps (Reference: Mongeの手引書 (“Monge manual,” in Japanese) by tatyam):

• Sort the lines in ascending order of their slopes \(\displaystyle \left(=\frac{A_i}{B_i}\right)\).
• Prepare an empty list \(L\) to manage the lines.
• For \(i=1,2,\ldots,N\), do the following:
  • Insert the line with the \(i\)-th smallest slope to \(L\).
  • Repeatedly remove the previous line while it is unnecessary.
• The final lines in \(L\) form the minimum values.

Let us redefine \(N\) as the number of lines in the resulting \(L\), denoting the \(i\)-th such line by \(A_ix+B_iy=C_i\).

Also, let \(x_i\) be the \(x\) coordinate of the intersection of the \(i\)-th and \((i+1)\)-th line, with fractional part rounded up, and \(x_0=-\infty\) and \(x_N=\infty\).

Then, using \(\displaystyle X_{\mathrm{max}}=\min_{1\le i\le N} \left\lceil \frac{C_i}{A_i} \right\rceil\), the answer to this problem turns out to be the sum of the contribution of each line, that is:

\[ \displaystyle \sum_{i=1}^N \sum_{x\in [x_{i-1}, x_i)\cap [1, X_{\mathrm{max}})}\left\lfloor \frac{C_i-1-A_ix}{B_i} \right\rfloor. \]

\(\displaystyle \sum_{x\in [x_{i-1}, x_i)\cap [1, X_{\mathrm{max}})}\left\lfloor \frac{C_i-1-A_ix}{B_i} \right\rfloor\) can be evaluated using the floor sum algorithm in \(O(\log A_i)\) time. Hence, this problem can be answered in a total of \(O(N(\log N+\log \max_i A_i))\) time per test case.

Sample code (Python 3)

from functools import cmp_to_key
import sys

input = sys.stdin.readline


def floor_sum(n, m, a, b):
    a1, a2 = a // m, a % m
    ans = n * (n - 1) // 2 * a1
    if a2 == 0:
        return ans + b // m * n
    b1, b2 = b // m, b % m
    y = (a2 * n + b2) // m
    ans += n * (y + b1) - floor_sum(y, a2, m, m + a2 - b2 - 1)
    return ans


def cmp(d1, d2):
    a1, b1, c1 = d1
    a2, b2, c2 = d2
    if a1 * b2 != a2 * b1:
        return a1 * b2 - a2 * b1
    return c1 * a2 - c2 * a1


def clamp(x, l, r):
    return min(r, max(l, x))


for _ in range(int(input())):
    N = int(input())
    L = [tuple(map(int, input().split())) for _ in range(N)]
    L.sort(key=cmp_to_key(cmp))
    co = []
    x = []
    INF = 10**18
    x_lim = INF
    for l in L:
        aj, bj, cj = l
        if len(co) >= 1:
            ai, bi, ci = co[-1]
            if ai * bj == aj * bi:
                continue
        while len(co) >= 2:
            ai, bi, ci = co[-1]
            xj = (bi * cj - bj * ci - 1) // (aj * bi - ai * bj) + 1
            if xj > x[-1]:
                break
            co.pop()
            x.pop()
        co.append(l)
        if len(x) == 0:
            x.append(-INF)
        else:
            ai, bi, ci = co[-2]
            xj = (bi * cj - bj * ci - 1) // (aj * bi - ai * bj) + 1
            x.append(xj)
        x_lim = min(x_lim, (cj + aj - 1) // aj)
    x.append(INF)
    ans = 0
    for i in range(len(co)):
        ai, bi, ci = co[i]
        le, ri = clamp(x[i], 1, x_lim), clamp(x[i + 1], 1, x_lim)
        n, m, a, b = ri - le, bi, ai, ci - 1 - ai * (ri - 1)
        ans += floor_sum(n, m, a, b % m) + (b // m) * n
    print(ans)