Pythagore 2

Nguồn: CLUE OJ – Chương 19: Đệ quy cơ bản Độ khó: Trung bình Số học Đệ quy sinh ước

Đề bài

Cho tam giác vuông có độ dài cạnh góc vuông là $x$, độ dài cạnh góc vuông còn lại là $y$ $(x < y)$. Đếm số cạnh góc vuông $y$ sao cho tồn tại cạnh huyền với độ dài $z$ là số nguyên và lấy $x, y$ là 2 cạnh góc vuông tương ứng.

Lưu ý: 3 cạnh $x, y, z$ đều là số nguyên.

Input: nhập vào số $x$ $(x \le 1000000)$.

Output: kết quả tương ứng với bài toán.

Giải thích ví dụ: với $x = 12$ có 2 bộ $(12, 16, 20)$ và $(12, 35, 37)$.

Ví dụ – input

12

Ví dụ – output

2

Lời mở đầu

Bài này nằm trong chương Đệ quy cơ bản nhưng bản chất là một bài số học: biến đổi định lý Pythagore thành bài đếm ước. Mình đi từ cách thử từng $y$ (dễ nghĩ nhưng chậm), tới cách thử từng ước, và cuối cùng là cách dùng đệ quy để sinh ước từ phân tích thừa số nguyên tố – đúng tinh thần của chương. Nếu bài này trên web CLUE OJ không nộp được thì các bạn nộp ở link Codeforces bên dưới nhé.

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.

Nộp bài trên CLUE OJ

Dành cho tất cả mọi ngườiNộp bài trên Codeforces

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.

Nộp bài trên Codeforces

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test100 testÝ tưởngx² = d·eCách 1thử yCách 2thử ướcCách 3đệ quyTổng kếtkết quả

Bộ testBộ test chính thức có gì?

Bộ test có 100 test, chia rất đều thành 5 mức độ lớn của $x$:

Test	x	Đáp án
1–20	0 … 95	0 … 9
21–40	170 … 999	1 … 18
41–60	1.063 … 9.419	1 … 41
61–80	10.274 … 86.792	1 … 101
81–100	154.549 … 1.000.000	1 … 66

• Test 1 là $x = 0$ (đáp án 0) – nhớ xử lý để không chia cho 0 hay lặp sai.
• Nhiều test có đáp án 1 hoặc 3, 4 (thường là $x$ nguyên tố hoặc có ít ước); test có đáp án lớn nhất là $x = 21060$ với 101 cách.

Đề không ghi subtask, mình chia 5 nhóm theo độ lớn của $x$ (kết quả chạy thật, giới hạn 1 giây):

Nhóm	Điều kiện	Test	Cách 1 (thử từng y)	Cách 2 (thử từng ước)	Cách 3 (đệ quy sinh ước)
1	$x < 10^2$	1–20	20/20	20/20	20/20
2	$x < 10^3$	21–40	20/20	20/20	20/20
3	$x < 10^4$	41–60	20/20	20/20	20/20
4	$x < 10^5$	61–80	4/20	20/20	20/20
5	$x \le 10^6$	81–100	0/20	20/20	20/20

Ý tưởngx² = (z − y)(z + y)

Từ $x^2 + y^2 = z^2$ ta có $x^2 = z^2 - y^2 = (z - y)(z + y)$. Đặt $d = z - y$ và $e = z + y$:

• $d \cdot e = x^2$ và $d < e$ (vì $y > 0$), nên $d < x$ – tức $d$ là một ước của $x^2$ nhỏ hơn $x$.
• $y = \dfrac{e - d}{2}$, $z = \dfrac{e + d}{2}$ là số nguyên khi và chỉ khi $d$ và $e$ cùng tính chẵn lẻ.
• Đề yêu cầu $y > x$, tức là $e - d > 2x$.

Kết luận

Đáp án = số ước $d$ của $x^2$ với $d < x$, sao cho $e = x^2 / d$ thoả $e - d$ chẵn và $\dfrac{e - d}{2} > x$. Mỗi $d$ như vậy cho đúng một $y$ (và $d$ khác nhau cho $y$ khác nhau).

Với $x = 12$, $x^2 = 144$: em bấm Tiếp để xem từng ước $d < 12$ được kiểm tra thế nào:

x =

Ví dụ nhanh:

Để ý cặp $d = 6, e = 24$ cho $y = 9 < 12$: đây là tam giác $(9, 12, 15)$, nhưng khi đó $12$ là cạnh lớn hơn nên không được đếm (đề bắt $x < y$).

Cách 1Thử từng y – $O(x^2)$

Cách dễ nghĩ nhất: thử mọi $y > x$, kiểm tra $x^2 + y^2$ có phải số chính phương không. Nhưng thử tới đâu thì dừng? Từ ý tưởng ở trên, $y = (x^2/d - d)/2 \le (x^2 - 1)/2$ (lớn nhất khi $d = 1$). Vậy chỉ cần thử $y$ từ $x + 1$ tới $(x^2 - 1)/2$.

C++▶ Chạy tay từng dòng codeCách 1: thử mọi y từ x + 1 tới (x² − 1)/2, kiểm tra x² + y² chính phương.

Dữ liệu vào (stdin) – sửa thoải mái12

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. sqrtl lấy căn bậc hai kiểu long double (chính xác hơn sqrt), ép về long long rồi kiểm tra lại bằng phép nhân z * z == t – không bao giờ so sánh số thực bằng ==.
2. Số lần lặp khoảng $x^2 / 2$: $x = 10^4$ là $5 \cdot 10^7$ lần (còn kịp), $x = 10^5$ đã là $5 \cdot 10^9$ lần – quá chậm.

Không gian$O(1)$

Thời gian$O(x^2)$

Kết quả chạy thật: Bản C++ đúng 64/100 test, quá thời gian ở test 61–65, 67–71, 75–100; test đúng chạy lâu nhất 0.99s. Bản Python: đúng 44/100 test, quá thời gian ở test 43–51, 53–57, 59–100; test đúng chạy lâu nhất 0.96s.

Cách 2Thử từng ước d < x – $O(x)$

Dùng thẳng kết luận ở phần ý tưởng: duyệt $d$ từ 1 tới $x - 1$, nếu $d$ chia hết $x^2$ thì tính $e$ và kiểm tra 2 điều kiện.

C++▶ Chạy tay từng dòng codeCách 2: duyệt d từ 1 tới x − 1, chỉ xét các d là ước của x².

Dữ liệu vào (stdin) – sửa thoải mái12

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. $x^2$ lên tới $10^{12}$ nên x2 phải là long long.
2. continue bỏ qua ngay các $d$ không phải ước – phần lớn các $d$ rơi vào trường hợp này.
3. $x = 0$ hoặc $x = 1$: vòng lặp không chạy lần nào, in 0 đúng.

Không gian$O(1)$

Thời gian$O(x)$

Kết quả chạy thật: Bản C++ đúng 100/100 test; test đúng chạy lâu nhất 0.01s. Bản Python: đúng 100/100 test; test đúng chạy lâu nhất 0.12s. Đây đã là lời giải full điểm.

Cách 3Đệ quy sinh ước từ thừa số nguyên tố

Cách 2 thử cả $x$ số $d$ nhưng $x^2$ chỉ có rất ít ước. Nếu $x = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$ thì $x^2 = p_1^{2a_1} \cdots p_k^{2a_k}$, và mỗi ước của $x^2$ có dạng $p_1^{b_1} \cdots p_k^{b_k}$ với $0 \le b_i \le 2a_i$. Ta sinh các ước bằng đệ quy: hàm gen(i, d) chọn số mũ cho thừa số thứ $i$, với $d$ là tích đã chọn từ các thừa số trước.

Hàm gen(i, d)

1. Nếu $d \ge x$: cắt nhánh (ta chỉ cần ước nhỏ hơn $x$, nhân thêm chỉ làm $d$ lớn hơn).
2. Nếu đã chọn xong số mũ cho mọi thừa số ($i$ = số thừa số): $d$ là một ước hoàn chỉnh → kiểm tra điều kiện.
3. Ngược lại: lần lượt thử $b = 0, 1, \ldots, 2a_i$, gọi gen(i + 1, d \cdot p_i^b).

C++▶ Chạy tay từng dòng codeCách 3: phân tích x ra thừa số nguyên tố, đệ quy gen(i, d) chọn số mũ để sinh các ước d < x của x².

Dữ liệu vào (stdin) – sửa thoải mái12

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Phân tích thừa số bằng cách chia thử tới $\sqrt{x}$; phần còn lại t > 1 là một thừa số nguyên tố lớn.
2. if (cur >= x) break; – lũy thừa đã vượt $x$ thì các lũy thừa cao hơn càng vượt, khỏi thử.
3. Số lời gọi đệ quy chỉ cỡ số ước của $x^2$ (với $x \le 10^6$ tối đa vài nghìn), nhanh hơn hẳn cách 2 khi $x$ lớn.

Không gian$O(\log x)$

Thời gian$O(\sqrt{x} + \text{số ước của } x^2)$

Kết quả chạy thật: Bản C++ đúng 100/100 test; test đúng chạy lâu nhất 0.00s. Bản Python: đúng 100/100 test; test đúng chạy lâu nhất 0.03s.

Tổng kếtKết quả chạy thật trên bộ test

Cách	Ngôn ngữ	Đúng	Lâu nhất	Ghi chú
1. Thử từng y	C++	64/100	> 1s	Quá thời gian test 61–65, 67–71, 75–100
	Python	44/100	> 1s	Quá thời gian test 43–51, 53–57, 59–100
2. Thử từng ước d < x của x²	C++	100/100	0.01s	Full điểm
	Python	100/100	0.12s	Full điểm
3. Đệ quy sinh ước từ thừa số nguyên tố	C++	100/100	0.00s	Full điểm
	Python	100/100	0.03s	Full điểm

Ghi chú của mình: cách 1 (thử từng $y$) qua trọn các test $x < 10^4$ và vài test $x \approx 1{,}1 \cdot 10^4$ – $1{,}5 \cdot 10^4$ (tổng 64/100 test), bản Python của nó chỉ qua các test $x < 10^3$ và vài test lẻ; cách 2 và cách 3 qua 100/100 test. Mấu chốt của bài là biến đổi $x^2 = (z - y)(z + y)$ và nhớ điều kiện $y > x$ (bỏ qua các cặp cho $y < x$). Test 1 có $x = 0$, đáp án 0.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇