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

HK boy viết 12:42 ngày 01/10/2018

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 =))

nắng viết 12:49 ngày 01/10/2018

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

HK boy viết 12:46 ngày 01/10/2018

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ự.

Bài liên quan
0