Tìm bcnn của số nguyên lớn

An_Nguyen · December 9, 2019, 3:39am

Mọi người cho e hỏi bài này với ạ?

Trong dịp Đại lễ 1000 năm Thăng Long - Hà Nội. An quan sát thấy nhiều đèn nhấp nháy được trang trí trên các đường phố. Vốn là một học sinh yêu thích môn Tin học và Vật lý. An quyết định tự tạo một dây đèn nhấp nháy đặc biệt. Dây đèn của An gồm n bóng nối tiếp nhau, đánh số thứ tự từ 1 đến n và được điều khiển theo nguyên tắc: Bắt đầu từ thời điểm 0 tất cả bóng đèn đều ở trạng thái tắt, bóng thứ i sẽ loé sáng vào các thời điểm t_i, 2t_i, 3t_i (i = 1,2,…,n). An chờ đợi và muốn biết thời điểm nào mà cả n bóng đều cùng loé sáng.

Ví dụ: nếu t₁ = 4 thì tại các thời điểm 4, 8, 12, 16, 20, … bóng đèn 1 sẽ loé sáng. t₂ = 6 thì tại các thời điểm 6, 12, 18, 24, 30, … bóng đèn 2 sẽ loé sáng. Như vậy, thời điểm 12 sẽ là thời điểm sớm nhất mà cả 2 bóng đèn đều cùng loé sáng.

Yêu cầu: Cho t₁, t₂, …, t_n, hãy giúp An tính thời điểm sớm nhất mà tất cả n bóng đèn đều loé sáng.
Dữ liệu: Vào từ file văn bản BAI1.INP có dạng:

Dòng đầu tiên chứa số nguyên dương n (2 ≤ n ≤ 30).

Dòng thứ hai chứa n số nguyên dương t₁, t₂,…, t_n (t_i ≤ 10⁶).

Kết quả: Ghi ra file văn bản BAI1.OUT thời điểm sớm nhất mà tất cả n bóng đèn đều loé sáng.

kisuluoibieng · December 2, 2019, 8:52am

bcnn(a, b) = a*b/ucln(a,b)

đặt x = bcnn(a, b)
bcnn(a, b, c) = x*c/ucln(x, c)

rogp10 · December 2, 2019, 9:03am

Phép chia phải thực hiện trước vì phép nhân sẽ ra số lớn, dù kết quả không lớn.

kisuluoibieng · December 2, 2019, 9:33am

rồi phép chia nó không chẵn thì sao?
nếu đã nói tới trường hợp đó thì sẽ phải tính đến chuyện kết quá lên tới ~10^180, phải xử lý số nguyên lớn bằng array hoặc (cấu trúc dữ liệu nào đó có thể đáp ứng được)

rogp10 · December 2, 2019, 9:35am

Chia cho ước chung lớn nhất thì sao lại không chẵn chứ

kisuluoibieng · December 2, 2019, 9:42am

ok, cả x và c đều chia hết cho số ước chung của nó
tính x/ucln(x, c) trước để để kết quả nó nhỏ một chút
sau đó nhân lại với c, thì có chắc là kết quả nó vẫn chứa được trong 1 biến không?

rogp10 · December 2, 2019, 11:24am

Vậy là phải nhắc lại

8_Naf · December 9, 2019, 3:39am

Một dãy các số nguyên dương thì TH BCNN của chúng lớn nhất là khi dãy toàn là các số nguyên tố cùng nhau (tức là chúng có UCLN = 1). Khi đó, BCNN(t1, t2, …, tn) = t1 * t2 * … tn.

Đề bài cho n <= 30 và t <= 10^6. Suy ra được BCNN < (10^6)^30, tức < 10^180 < Double max value (≈10^308). Vậy thay vì truyền vào số nguyên, bạn nên truyền double vào.

Kiểu double thì C++ không có định nghĩa toán tử % (khi tính UCLN thì dùng cần nó), bạn có thể thay thế bằng:

double tmp = a/b; //Tạo biến tạm để tránh sai số
double _trunc = trunc(tmp); //Tạo biến tạm để tránh sai số
a = a - _trunc;

Để cho an toàn, sau khi bạn tính ra được BCNN rồi, thì ép nó vào string, rồi xoá những số dư thừa ở sau dấu chấm và xoá cả dấu chấm (vì BCNN là số nguyên nên không khể có phần thập phân được).

tntxtnt · December 8, 2019, 5:05pm

kiểu double đâu có chính xác tới 180 chữ số đâu em :V ví dụ viết số A vô ga drô là 6.023 x 10^23 thì tuy độ lớn nó tới 10^23 nhưng nó chỉ chính xác tới 4 chữ số 6,0,2,3 à :V Kiểu double cũng vậy, tuy độ lớn có thể tới 10^308 nhưng chính xác chỉ được 15-16 chữ số à

8_Naf · December 9, 2019, 3:04am

Hi hi quên mất độ chính xác, vậy phải dùng chuỗi rồi, mệt đây