---
# System prepended metadata

title: Sửa bài 17/4

---

## Bài 4: Cạnh góc vuông (THTB Sơn Trà, Đà Nẵng 2024)
### 1. Yêu cầu đề
- Cho 1 số nguyên dương n. 
- Tìm số cặp (x,y) nguyên dương sao cho n<sup>2</sup> +  x<sup>2</sup> = y<sup>2</sup>
n<sup>2</sup> = y<sup>2</sup> - x<sup>2</sup>
=> n<sup>2</sup> = (y-x)(y+x)
Gọi: 
a = y-x
b = y+x
=> n<sup>2</sup> = a*b
vì y và x nguyên dương nên y-x và y+x là số nguyên
=> a và b là số nguyên
=> Bài toán tìm số lượng ước của n<sup>2</sup>

a = y-x
b = y+x
Cộng vế theo vế:
a + b = 2y => y = (a+b)/2
Trừ vế theo vế:
a - b = -2x => x = (b-a)/2
=> (a+b) % 2 = 0 và (b-a) % 2 = 0
=> a và b luôn cùng chẳn hoặc cùng lẻ

### 2. Cách làm
- B1: Đếm số lượng ước của n<sup>2</sup>
Để đếm được số lượng ước số thì phân tích n<sup>2</sup> thành thừa số số nguyên tố
Gọi Pi là 1 tsnt bất kỳ của n^2 
Mi là mũ của Pi
N = (M1+1)(M2+1)(M3+1)+..

![Screenshot 2024-04-17 at 6.10.51 PM](https://hackmd.io/_uploads/HkDB0magA.png)

n = 20 
2^2 * 5
N = (2+1)(1+1) = 6
20 = 1 2 4 5 10 20

n<sup>2</sup> = n * n

n * n = 400
2^4 * 5^2

- B2: Chia trường hợp với tất cả các ước của n<sup>2</sup> đều lẻ hoặc có chẵn
Với trường tất cả đều lẻ thì số lượng cặp (a,b) = số lượng ước số của n<sup>2</sup>/2
Ngược lại với trường hợp có chẵn thì ta bỏ trường hợp ước chẵn nằm về 1 bên a hoặc b. Xử lý bằng cách loại đi 1 trường hợp số 2 ở trong việc đếm ước
##### Code:

```python=
n = int(input())
x = n
a = [0] * (10**6+5)

#phan tich thua so nguyen to
for i in range(2,int(n**0.5)+1):
    while n % i == 0:
        n //= i
        a[i] += 1

# kiem tra neu khi phan tich tsnt ma ton tai tsnt lon hon 10**6
if n > 1 and n > 10**6:
    a[0] = 1
else:
    a[n] = 1
#nhan doi 
for i in range(10**6+1):
    a[i] *= 2
#dem so luong uoc
d = a[0]+1

for i in range(3,10**6+1):
    if a[i]>0:
        d *= (a[i]+1)
#ap dung cach chia cap
if a[2] == 0: 
    print(d//2)
else: 
    print((a[2]-1)*d//2)
```
