Bài toán dcg

Tác giả:

Dạng bài

Điểm: 100 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Hôm nay, trong lúc rảnh rỗi, TK_Thanh_Son đã nghĩ ra 1 bài toán để đố bạn cậu ấy NTT_36.
Bài toán được TK_Thanh_Son đặt ra như sau: Tìm 2 số nguyên dương \(a, b\) bất kỳ biết: \(BCNN(a, b) = N\) và \(ƯCLN(a, b) = M\)
Vì bài toán này quá dễ nên NTT_36 bảo TK_Thanh_Son tăng độ khó lên. Sau khi cải tiến, bài toán được đặt ra đã trở thành:
Tìm số lượng cặp số \(a\), \(b\) nguyên dương thỏa mãn \(BCNN(a, b) = N\) và \(ƯCLN(a, b) = M\).
Sau khi TK_Thanh_Son đưa ra bài toán này, NTT_36 đã phải chịu thua và nhờ các bạn giải giúp

Input

Dòng đầu tiên chứa số nguyên dương \(N\)
Dòng thứ hai chứa số nguyên dương \(M\)

Output

Một dòng duy nhất là số lượng cặp số \(a\) và \(b\) thỏa mãn
\(Ràng buộc\)
\(0 < N, M \le 10 ^ {10}\)

Example

Test 1

Input

180
12

Output

Note

Cặp \((a, b)\) và \((b, a)\) được tính là 2 cặp khác nhau

Bình luận

-2

baonhat 2:46 p.m. 19 Tháng 10, 2024

mình xin chia sẻ code cho những bạn làm ko đc:
N, M = int(input()), int(input())
c = 0
if N % M == 0:
t = N // M
for x in range(1, int(t**0.5) + 1):
if t % x == 0:
y = t // x
a, b = x, y
while b:
a, b = b, a % b
if a == 1:
if x != y:
c += 2
else:
c += 1
print(c)
giaỉ thích:
Mối quan hệ cơ bản:
BCNN(a,b) * UCLN(a,b) = a * b
Trong bài toán này, BCNN(a,b) = N và UCLN(a,b) = M, nên:
N * M = a * b

Vì UCLN(a,b) = M, nên a và b phải có dạng:
a = M * x
b = M * y
Trong đó x và y là các số nguyên dương và UCLN(x,y) = 1

Thay vào công thức ở bước 1:
N * M = (M * x) * (M * y)
N = M * x * y

Vậy bài toán trở thành tìm số cặp (x,y) sao cho:
x * y = N / M và UCLN(x,y) = 1

Để tìm các cặp (x,y) này, ta duyệt qua các ước của N/M:

Duyệt từ 1 đến căn bậc hai của N/M để tìm tất cả các ước.
Với mỗi ước x, tính y = (N/M) / x
Kiểm tra xem UCLN(x,y) có bằng 1 không
Nếu bằng 1, ta đã tìm được một cặp hợp lệ
Đếm số cặp:

Nếu x ≠ y, ta có 2 cặp hợp lệ: (x,y) và (y,x)
Nếu x = y, ta chỉ có 1 cặp hợp lệ: (x,x)
Tại sao dùng vòng lặp while để tính UCLN:
Đây là thuật toán Euclid để tính UCLN, hiệu quả hơn so với các phương pháp khác.

Tại sao chỉ duyệt đến căn bậc hai của N/M:

Nếu x là ước của N/M, thì y = (N/M)/x cũng là ước.
Bằng cách này, ta tìm được tất cả các cặp ước mà không cần duyệt hết N/M.
Tóm lại, phương pháp này tận dụng các tính chất của UCLN và BCNN để chuyển bài toán thành việc tìm các cặp ước của N/M có UCLN bằng 1. Cách tiếp cận này hiệu quả hơn nhiều so với việc thử tất cả các cặp số có thể.