P13769 [CERC 2021] Lines in a grid
题目描述
假设我们有一个 $n \times n$ 的整数网格，例如 $\{(i, j)\}_{i=0, j=0}^{n-1, n-1}$。令 $l_n$ 表示与网格上至少两个点相交的不同直线的数量。
对于 $n = 3$，恰好有 $20$ 条这样的直线，如下图所示。
:::align{center}
:::
请计算所有给定 $n$ 的 $l_n$。
输入格式
第一行包含一个整数 $Q$，表示询问的数量。第二行包含 $Q$ 个用空格分隔的整数 $n_1, \ldots, n_Q$。
输出格式
输出 $Q$ 行，每行一个数，依次为 $l_{n_1}, \ldots, l_{n_Q}$。由于 $l_k$ 可能很大，请对 $10^6 + 3$ 取模后输出。
说明/提示
### 输入范围
- $1 \leq Q \leq 1000$
- $1 \leq n_i \leq 10^7$
由 ChatGPT 4.1 翻译