Tích riêng | Câu 4 Đề HSG tin 11 Nghệ An | Năm 2014 - 2015

Đề bài. (3 điểm) Tích riêng                                                                      

Lời giải:

def tich_chu_so(n):
    res = 1
    while n > 0:
        res *= n % 10
        n //= 10
    return res

def tich_rieng(n):
    return n * tich_chu_so(n)

def tim_so(x,y):
    count = 0
    for i in range(1,y+1):
        if '0' in str(i):
            continue
        elif tich_rieng(i) >= x and tich_rieng(i) <= y:
            count += 1
    return count

if __name__ == "__main__":
    with open("TICH.INP", "r") as f:
        A, B = map(int, f.readline().split())

    with open("TICH.OUT", "w") as f:
        f.write(str(tim_so(A, B)))

Giải thích: Trong code trên hàm tim_so chỉ tìm các số có chữ số khác 0 và những số nhỏ hơn hoặc bằng b. Vì những số có chữ số là 0 thì tích riêng chắc chắn bằng 0, còn lại những số lớn hơn b thì tích riêng sẽ lớn hơn b.

Thuật toán đệ quy và code mẫu bằng Pascal.

program TICH_RIENG;
const   fi = 'TICH.inp';
        fo = 'TICH.out';
var
   memo : array[0..17,0..29,0..18,0..12,0..10] of int64;
   f : array[1..4] of longint = ( 2, 3, 5, 7 );
   k : array[1..4] of longint = ( 0, 0, 0, 0 );
   code : array[0..9,1..4] of longint = (
      ( 0, 0, 0, 0 ),
      ( 0, 0, 0, 0 ),
      ( 1, 0, 0, 0 ),
      ( 0, 1, 0, 0 ),
      ( 2, 0, 0, 0 ),
      ( 0, 0, 1, 0 ),
      ( 1, 1, 0, 0 ),
      ( 0, 0, 0, 1 ),
      ( 3, 0, 0, 0 ),
      ( 0, 2, 0, 0 )
   );
function rec( digits : longint; a, pot, lo, hi : int64 ) : int64;
var
   b : int64;
   memoize, ok : boolean;
   digit, i : longint;
begin
   b := a + pot-1;
   if (a > hi) or (b < lo) then begin
      rec := 0;
      exit;
   end;

   if digits = 18 then begin
      if (k[1] > 0) or (k[2] > 0) or (k[3] > 0) or (k[4] > 0) then rec := 0 else rec := 1;
      exit;
   end;

   if (a >= lo) and (b <= hi) then memoize := true else memoize := false;

   if memoize and (memo[digits,k[1],k[2],k[3],k[4]] >= 0) then begin
      rec := memo[digits][k[1]][k[2]][k[3]][k[4]];
      exit;
   end;

   pot := pot div 10;

   rec := 0;

   for digit := 0 to 9 do begin
      if (digit = 0) and (a <> 0) then continue;

      ok := true;
      for i := 1 to 4 do
         if code[digit,i] > k[i] then ok := false;
      if not ok then continue;

      for i := 1 to 4 do k[i] := k[i] - code[digit,i];
      rec := rec + rec( digits+1, a + digit*pot, pot, lo, hi );
      for i := 1 to 4 do k[i] := k[i] + code[digit,i];
   end;

   if memoize then memo[digits,k[1],k[2],k[3],k[4]] := rec;
end;

var
   lo, hi, rjesenje : int64;

function ceil( a, b : int64 ) : int64;
begin
   ceil := (a+b-1) div b;
end;

function floor( a, b : int64 ) : int64;
begin
   floor := a div b;
end;

procedure gen( limit, product : int64; factor : longint );
begin
   if (product > 1000000000) or (product*product > limit) then exit;

   if factor > 4 then begin;
      rjesenje := rjesenje + rec( 0, 0, 1000000000000000000, ceil(lo,product), floor(hi,product) );
   end else begin
      gen( limit, product, factor + 1 );
      inc( k[factor] );
      gen( limit, product*f[factor], factor );
      dec( k[factor] );
   end;
end;

   var dig, a, b, c, d : longint;
begin
   assign(input,fi);
   reset(input);
   assign(output,fo);
   rewrite(output);
   readln( lo, hi );

   for dig := 0 to 17 do
   for a := 0 to 29 do
   for b := 0 to 18 do
   for c := 0 to 12 do
   for d := 0 to 10 do
      memo[dig,a,b,c,d] := -1;

   gen( hi, 1, 1 );

   writeln( rjesenje );
end.

Biến

• memo: Mảng 5 chiều lưu trữ kết quả của các giá trị đã tính trước đó.
• f: Mảng các số nguyên tố 2, 3, 5 và 7.
• k: Mảng theo dõi số lần mỗi số nguyên tố đã được sử dụng trong một số.
• code: Mảng cho biết liệu một chữ số có chia hết cho bất kỳ số nguyên tố nào hay không.
• lo: Giới hạn dưới của khoảng.
• hi: Giới hạn trên của khoảng.
• rjesenje: Số lượng tích riêng trong khoảng lo; hi.

Hàm

• rec: Hàm đệ quy tính số lượng tích riêng trong khoảng [lo, hi].
• ceil: Hàm trả về số nguyên nhỏ nhất lớn hơn hoặc bằng một số cho trước.
• floor: Hàm trả về số nguyên lớn nhất nhỏ hơn hoặc bằng một số cho trước.
• gen: Hàm tạo ra tất cả các tích riêng trong khoảng.