Tìm hướng giải cho bài toán tối giản phân số a/b + c/d

[oggyggbond123 (Lê Đạt)]

Hướng giải sao nhỉ mọi người …?

[Sherly1001]

Tính như thường rồi tối giản bằng cách chia cả tử và mẫu cho ước chung lớn nhất của chúng.

[SITUVN.gcd]

1. Cộng phân số (quy đồng mẫu số).
2. Tối giản. Tính ước chung lớn nhất của tử và mẫu. Chia cả tử và mẫu cho UCLN.

[tntxtnt]

a b c d có thể lên tới 10^10 kìa, ko tính tử và mẫu rồi tìm ucln được :V Ví dụ mẫu số bd lên tới 10^20 số nguyên 64-bit cũng ko chứa nổi :V

[rogp10]

Bài này là 64x64 -> 128 cẩn thận xíu thôi

Do để uint64_t thì chỉ lên 1.6*10^19 là hết.

[Nho_Huu]

Tạo ra 1 mảng số nguyên tố, tối giản hai phân số rồi tìm bội số chung nhỏ nhất của mẫu, quy đồng và cộng lại là xong.

[rogp10]

Cái mảng chắc không cần đâu

[Nho_Huu]

ko cần tối giản phân số làm sao dc
mảng đó phải dùng nhiều lần chứ ko phải 1 lần đâu

[rogp10]

Bài này precomputation cũng không giúp được nhiều.

[Nho_Huu]

thuật toán đó như thế nào?