19 . 數論初心者

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

kenkenken
Caidorz

User's AC Ratio

97.9% (46/47)

Submission's AC Ratio

71.3% (122/171)

Tags

ioicamp ioicamp-2024

Description

給你一個正整數 $N$，你能算出有幾組正整數解 $(x, y, z)$ 同時滿足以下的兩個條件嗎？
$$
\begin{cases}
\gcd(x, y) + z = \gcd(y, z) + x = \gcd(z, x) + y \\
1 \leq x, y, z \leq N
\end{cases}
$$

Input Format

輸入的第一行恰有一個正整數 $T$ ，表示這份檔案的測資數量。

輸入接下來 $T$ 行的每一行都恰有一個正整數 $N$ ，代表給定的正整數 $N$。

  • $1 \le T \le 10^ 5$
  • $1 \le N \le 10^ 6$

Output Format

對於 $T$ 筆測試資料，請輸出每一筆的答案，意即滿足條件的數組 $(x, y, z)$ 的合法解個數。

Sample Input 1

1
2

Sample Output 1

5

Sample Input 2

1
240128

Sample Output 2

8555996

Sample Input 3

2
2
240128

Sample Output 3

5
8555996

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 3~18 $T = 1, N \leq 100$ 20
3 3~33 $T = 1$ 50
4 3~46 無額外限制 30

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1
1 1000 262144 65536 1
2 1000 262144 65536 1
3 1000 262144 65536 2 3 4
4 1000 262144 65536 2 3 4
5 1000 262144 65536 2 3 4
6 1000 262144 65536 2 3 4
7 1000 262144 65536 2 3 4
8 1000 262144 65536 2 3 4
9 1000 262144 65536 2 3 4
10 1000 262144 65536 2 3 4
11 1000 262144 65536 2 3 4
12 1000 262144 65536 2 3 4
13 1000 262144 65536 2 3 4
14 1000 262144 65536 2 3 4
15 1000 262144 65536 2 3 4
16 1000 262144 65536 2 3 4
17 1000 262144 65536 2 3 4
18 1000 262144 65536 2 3 4
19 1000 262144 65536 3 4
20 1000 262144 65536 3 4
21 1000 262144 65536 3 4
22 1000 262144 65536 3 4
23 1000 262144 65536 3 4
24 1000 262144 65536 3 4
25 1000 262144 65536 3 4
26 1000 262144 65536 3 4
27 1000 262144 65536 3 4
28 1000 262144 65536 3 4
29 1000 262144 65536 3 4
30 1000 262144 65536 3 4
31 1000 262144 65536 3 4
32 1000 262144 65536 3 4
33 1000 262144 65536 3 4
34 1000 262144 65536 4
35 1000 262144 65536 4
36 1000 262144 65536 4
37 1000 262144 65536 4
38 1000 262144 65536 4
39 1000 262144 65536 4
40 1000 262144 65536 4
41 1000 262144 65536 4
42 1000 262144 65536 4
43 1000 262144 65536 4
44 1000 262144 65536 4
45 1000 262144 65536 4
46 1000 262144 65536 4
Submit
Back to Top