SQRT + SQRT = SQRT? (bản khó)
Xem PDF
Nộp bài
Điểm:
1500
Thời gian:
3.0s
PyPy3
6.0s
Python
6.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Tác giả:
Dạng bài
Các bài G, H, I chỉ khác nhau ở giới hạn của c.
Cho số nguyên không âm c, bạn cần đếm xem có bao nhiêu số nguyên không âm a ≤ c sao cho (\sqrt c - \sqrt a)^2 là một số nguyên, hay nói cách khác tồn tại số nguyên không âm b sao cho \sqrt a + \sqrt b = \sqrt c.
Input, Output và Subtask:
Input:
- Dòng đầu tiên chứa số nguyên T\leq 100, miêu tả số testcases.
- T dòng tiếp theo, mỗi dòng gồm 1 số nguyên không âm c.
Output:
Gồm T dòng, mỗi dòng là số các số nguyên dương a thõa mãn điều kiện, sắp xếp theo thứ tự không giảm.
Subtask:
Với bản khó, c\leq 10^{18}
Sample:
Input:
5
5
10
15
20
25
Output:
2
2
2
3
6
Notes:
-
\sqrt{0} + \sqrt{5} = \sqrt{5}
-
\sqrt{0} + \sqrt{10} = \sqrt{10}
-
\sqrt{0} + \sqrt{15} = \sqrt{15}
-
\sqrt{0} + \sqrt{20} = \sqrt{5} + \sqrt{5} = \sqrt{20}
-
\sqrt{0} + \sqrt{25} = \sqrt{1} + \sqrt{16} = \sqrt{4} + \sqrt{9} = \sqrt{25}
Bình luận