01/10/2018, 10:34
Thảo luận và tìm lỗi sai của code bài findnum
Cho trước một số n. Hãy tìm số nguyên dương nhỏ nhất có đúng n ước.
Dữ liệu vào
– Một số nguyên n duy nhất (1 ≤ n ≤ 1000).
Dữ liệu ra
– Số nguyên dương nhỏ nhất (không vượt quá 10^18) có đúng n ước.
(Biết rằng kết quả của các test luôn nằm trong giới hạn của đề)
Ví dụ
Input:
4
Output:
6
mọi người giúp mình tìm lỗi sai và nghĩ hướng giải nhanh hơn giúp mình với ạ
fo='data.out';
max=1000000000000000000;
var x:array[1..9]of longint=(2,3,5,7,11,13,17,19,23) ;
k:array[1..9] of longint;
s,sum:qword;n,i:longint;f:text;
procedure doctep;
begin
assign(f,fi);reset(f);
readln(f,n);
close(f);
end;
function lt(n,k:longint):qword;
var i:longint;
begin
lt:= 1;
if k= 0 then exit ;
for i:= 1 to k do lt:= lt*n;
end;
function init(n:longint):byte;
var dem:byte;
begin
dem:= 0;
while n<>1 do
begin
n:= n div 2;
inc(dem) ;
end;
exit(dem);
end;
procedure update; forward;
procedure attempt(i:longint);
var j:longint;
begin
for j:= 0 to 59 do
begin
if n mod (j+1) =0 then
begin
n:= n div (j+1);
k[i]:= j;
if i= 1 then update
else attempt(i-1);
n:= n*(j+1);
end
else if n=j then exit;
end;
end;
procedure update;
begin
if n<> 1 then exit;
s:= 1;
for i:= 1 to 9 do
s:= s*lt(x[i],k[i]) ;
if s<sum then sum:= s;
end;
procedure ghitep;
begin
assign(f,fo) ;rewrite(f);
sum:= max+1;
attempt(init(n));
writeln(f,sum);
close(f);
end;
begin
doctep;
ghitep;
end.
Hàm init(n) để tìm số số nguyên tố cần dùng
attempt(i) là quay lui
Bài liên quan
Mình chỉ nhớ cách nhanh hơn là quy hoạch động. Còn quy hoạch động thế nào thì phụ thuộc vào code backtrack của bạn =))
cảm ơn bạn mình tìm đc lỗi sai rồi.làm nộp đc 90 mà hoảng.mà cho mình hỏi cách qhđ thì thời gian là bao nhiêu.vì mình thấy cách này thời gian thực hiện là 0,01s
QHĐ nhanh hơn. 0.01s là thời gian nộp những test còn lại, còn test cuối bị chết. Tuy nhiên SPOJ chỉ tính thời gian những test sống.
Test trên SPOJ khá yếu, bạn lên codeforces tìm bài tương tự.