[Q] So anh em

[command29_10]

Hai so a va b goi la 2 so anh em khi:
a = tong cac uoc cua b.
b = tong cac uoc cua a.
Viet chuong trinh (Pascal) nhap vao 2 so a va b.
Cho biet 2 so do co phai la 2 so anh em khong?
**Chuong trinh dat toc do toi uu**

[skywalker]

hai số a,b có giới hạn <= 2 tỉ như bài số hoàn thiện ko

[Zero]

OK tốc độ cực nhanh đây

var

a,b,i,ta,tb : longint;

begin

write(' So thu nhat = ');
readln(a);

write(' So thu hai = ');
readln(b);

ta:=1;

for i:=2 to trunc(sqrt(a)) do
if a mod i = 0 then
begin
inc(ta,i);
if i <> a div i then inc(ta,a div i);
end;

tb:=1;

for i:=2 to trunc(sqrt(b)) do
if b mod i = 0 then
begin
inc(tb,i);
if i <> b div i then inc(tb,b div i);
end;

if (a = tb) and (b = ta) then writeln(a,' va ',b,' la hai so anh em')
else writeln(a,' va ',b,' khong la hai so anh em')


end.

Độ phức tạp của cách này chỉ là O(sqrt(a) + sqrt(b))

[Mad Dragon]

A ha bài này tui vừa mới thi vào cấp 3 đây,hồi ấy dốt đặc nên lãnh con 1 liền :)

[Junior IT]

Neu mo rong de bai them mot chut, nhap 2 so tu nhien (1<=b<=k<=2 ty) Hay in tat ca nhung cap so anh em trong doan [b,k] . Van phai la` thuat toan toi uu :question:

[command29_10]

Nay, lam sao lai viet dang Inc(ta,ta div i) duoc. Viet nhu vay khong dung roi. Viet lai di cho de hieu hon.

[Junior IT]

command29_10: Viet nhu vay chuong trinh van chay tot, dau co gi` dau ?:D
Zero: thuat toan cua ban chay rat nhanh, nhu*ng co mot so ket qua sai, vi' du : 1 va 1, 6 va 6 >>ko phai la cap so anh em (chuong trinh cua ban tra loi cac cap so do la` anh em :question: )

[command29_10]

Inc(ta,a div i) ma noi la chay tot a. a div i lam sao inc duoc.

[command29_10]

Hinh nhu cac so anh em deu cung chan hoac cung le het thi phai?

[Junior IT]

Ban cu test thu cai chuong trinh truoc di, minh chay thu roi
inc(ta,a div i) viet dung cu' phap dau co gi sai dau? Dung, cac so anh em deu cung chan hoac cung le (phan lon la chan) va tong cua 2 so anh em bat ky deu chia het cho 9, nhu*ng doi voi bai nay ~ diem dac biet tren ve so anh em ko co' ta'c dung cai thien duoc chuong trinh chay nhanh

[Zero]

Mình có viết 1 chương trình tìm thử số anh em trong phạm vi cho trước như Junior IT nói nhưng trình đấy viết rất thô chỉ chạy được với khoảng 1000 000 thôi.

Junior IT : ? mình thử tay đâu có sai nhỉ ? chương trình này mình mới chỉ viết chứ chưa hề chạy thử để về mình thử chạy coi.

[Junior IT]

Zero: theo ly thuyet ben Toan thi 1-1 va 6-6 ko phai la so anh em nhu*ng chuong trinh cua ban tra loi 2 cap so do la` so anh em >> ban chua xet nhung truong hop dac biet nhu so 1 va so 6

[Zero]

Ừm quên mất đó là trường hợp các số hoàn thiện nếu vậy chỉ cần thêm một đoạn if nưa là xong thôi.

[Junior IT]

Em có nhầm lẫn một chút, sorry Zero nhe'
A`, Zero cho mình xin cái source mà bạn viết chương trình tìm số anh em trong doan [1..100000] ko? Cám ơn bạn nhé. Email của mình: junior_it@movemail.com hoặc junior1402@lycos.com :D

[command29_10]

Zero, cho minh doan source nua di. Cam on ban nhe.
Dia chi mail: hung_02@yahoo.com
hung29_10@hotmail.com