시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
8 초 (추가 시간 없음) | 1024 MB | 32 | 18 | 13 | 52.000% |
Suppose that we are given a $n × n$ integer grid, e.g. $\{(i, j)\}_{i=0, j=0}^{n-1, n-1}$. Let $l_n$ be the number of different lines that intersect with at least two points on the grid.
For $n = 3$, there are exactly $20$ such lines, as drawn on the image below.
Compute $l_n$ for all given $n$.
First line contains an integer $Q$ – the number of queries. The second line contains $Q$ space-separated integers $n_1, \dots , n_Q$.
Print $Q$ numbers $l_{n_1} , \dots , l_{n_N}$, each in its own line. Since $l_k$ can be large, print them modulo $10^6 + 3$.
3 1 3 2
0 20 6
ICPC > Regionals > Europe > Central European Regional Contest > CERC 2021 G번