27 . 又是一道數學題？

Submit out of contest
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Chung0928

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

52.9% (9/17)

Tags

Description

給定 $k$，問有多少組 $(x,\ y)$ 且 $1 \le x \le y$，滿足 $x$$2$ $ + y$$2$ $ = k$$2$。
雖然大家還沒學到 TLE 的概念，但如果你在這題拿到了 TLE，你只要知道你的程式碼跑太慢了，請你優化你的做法。
有一個很好判斷會不會 TLE 的方式是判斷你的程式碼是否執行了超過 $10$$8$ 左右的操作。
因為 Cheng 還沒教你怎麼算時間複雜度，所以你只要會解 $1 \le k \le 10$$3$ 的情況就可以在這題拿到 90 分了！

對於所有測試資料：
$1 \le k \le 10$$6$

Input Format

輸入僅一行，
第一行有一個數字，代表 $k$。

Output Format

輸出一個數字代表答案

Sample Input 1

65

Sample Output 1

4

Hints

範例測資 1 解釋：
共有四組 $(x,\ y)$，
分別為
$(16, 63),\ (25,\ 60),\ (33,\ 56),\ (39,\ 52)$

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~24 $k \le 10$$3$ 90
2 0~49 題目範圍限制 10

Testdata and Limits

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