Phân tích m về thừa số nguyên tố, rồi tìm ước thông qua các số nguyên tố đó! nhưng mình vẫn chưa thể làm tối ưu hóa nó lên đc!
vd: n=20, phân tích thành 20=2,2,5 thì có các ước là 2, 5, 2*2=4, 2*5=10, 2*2*5=20( 1 thì bỏ qua).
Phân tích m về thừa số nguyên tố, rồi tìm ước thông qua các số nguyên tố đó! nhưng mình vẫn chưa thể làm tối ưu hóa nó lên đc!
vd: n=20, phân tích thành 20=2,2,5 thì có các ước là 2, 5, 2*2=4, 2*5=10, 2*2*5=20( 1 thì bỏ qua).
Bạn xem thử chương trình này nha
var M,N:longint;
fin,fout:text;
ptN:array[1..100000000] of longint; c_n:longint;
ptM:array[1..100000000] of longint; c_m:longint;
k:longint;
i,j,f:longint;
begin
assign(fin,'TIMK.INP');
assign(fout,'TIMK.OUT');
reset(fin);
read(fin,N); read(fin,M);
close(fin);
FillChar(ptM,sizeof(ptM),0);
FillChar(ptN,sizeof(ptN),0);
For i:=2 to N do
begin
j:=i; f:=2;
while j<>1 do
begin
If j mod f = 0 then
begin
If j<100000000 then inc(ptN[f])
Else c_n:=j;
j:=j div f;
end
Else inc(f);
end;
end;
f:=2;
while M<>1 do
begin
If M mod f = 0 then
begin
If j<100000000 then inc(ptM[f])
Else c_m:=M;
M:=M div f;
end
Else inc(f);
end;
For i:=2 to 100000000 do
If ptN[i]<>0 then writeln(i,' ',ptN[i]);
writeln;
For i:=2 to 100000000 do
If ptM[i]<>0 then writeln(i,' ',ptM[i]);
If (c_m<>0) and (c_m<>c_n) then k:=0
Else
begin
k:=0;
For i:=2 to 100000000 do
begin
If ptM[i]>ptN[i] then begin k:=0; break; end;
If ptM[i]<>0 then
If k=0 then k:=ptN[i] div ptM[i]
Else If ptN[i] div ptM[i] < k then k:= ptN[i] div ptM[i];
end;
end;
rewrite(fout);
write(fout,k);
close(fout);
end.
Bài này tớ làm sao báo lỗi không thực hiện được (giải thuật đệ quy)
Bài : Cho một xâu S (chỉ gồm các kí tự từ ‘0’ đến ‘9’, độ dài nhỏ hơn 10) và số nguyên M, hãy đưa ra một cách chèn váo s các dấu ‘+’,’-‘ để thu được số M cho trước
ví dụ: M=8, s=’123456789’ một cách chèn -1+2-3+4+5-6+7
.
