Need Help

[minato12]

Cho A thuộc N ( A<=10^3000 ). Tìm B lớn nhất sao cho B^2 <= A. Các bạn giúp mình bài này nhé

[Long_Phung]

tiêu đề không rõ ràng chi hết!
- Xét lùi từ (A/2) trở xuống.( B)
- xét B^2 với A.
- nhỏ hơn A thì Stop.

Có thể dùng đệ quy hoặc đơn giản là White.. do. Repeat... until.

[minato12]

tiêu đề không rõ ràng chi hết!
- Xét lùi từ (A/2) trở xuống.( B)
- xét B^2 với A.
- nhỏ hơn A thì Stop.

Có thể dùng đệ quy hoặc đơn giản là White.. do. Repeat... until.

Bạn ơi, giới hạn A lớn nhất là 10^3000 đấy!!! Bạn mà xét lui B=A/2 trở xuống thì xét tới ngày mai cũng ko ra được đâu.

[quangtq]

Xét từ Round(sqrt(A)) thôi.
Đảm bảo khoảng 1s là cùng.

[minato12]

Xét từ Round(sqrt(A)) thôi.
Đảm bảo khoảng 1s là cùng.
Nếu vậy phải viết hàm xử lí số lớn rùi hix hix :( A <= 10^3000 tức là có đến 3001 chữ số lận :(

[mr_invincible]

Xét từ Round(sqrt(A)) thôi.
Đảm bảo khoảng 1s là cùng.

=) vấn đề là đang cần tính cái này mà em. Hàm sqrt với hàm round của em là hàm gì mà tính được với số nguyên có 3000 chữ số +_+

Cách làm:
Cách 1: chặt nhị phân.
Cách 2: Ta lần lượt tính từng chữ số của B theo phương pháp duyệt từ 0 -> 9. Độ phức tạp 3000*10. Chạy khoảng 0.01 giây (không kể máy quá chậm).
Xét A có chẵn chữ số, nếu A có lẻ chữ số có thể làm tương tự.
Đầu tiên lấy 2 chữ số đầu tiên để khai căn. Tiếp theo mỗi lần lấy thêm 2 chữ số của A. Áp dụng thêm (x+1)^2 = x*x + 2*x + 1. Tư tưởng chính là thế. Để cài đặt được cụ thể các bạn cần suy nghĩ thêm

[quangtq]

Anh Trung pro vãi.
Em không nghĩ đến.
Rủ anh Vũ, QA sang đây cho vui :D

[technolt]

Bài này đúng như RR nói có thể dùng bài CP ở VOJ để giải
hoặc chặt nhị phân để giải
Nếu dùng chặt nhị phân thì phải cài nhân số lớn và chia số lớn cho 2

[mr_invincible]

Nhầm. Cách mình ở trên là 3000^2*10. Số lớn đến 10^3000 thì chỉ có cách trên để giải thôi. Chặt nhị phân là O(log(10^3000)*3000^2) = O(3000^3)