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.

Nếu thấy hữu ích, xin đừng tiếc cho tôi xin một ĐĂNG KÝ KÊNH và một LIKE. Xin cảm ơn!

Học mãi