CHUYÊN ĐỀ TIN HỌC 2021 - 2022: toán học rời rạc ứng dụng trong tin học, CHUYÊN ĐỀ SỐ HỌC

[Yopovn]

CHUYÊN ĐỀ TIN HỌC 2021 - 2022: toán học rời rạc ứng dụng trong tin học, CHUYÊN ĐỀ SỐ HỌC

CHUYÊN ĐỀ SỐ HỌC

Bài 1 : Amount of Degrees​

Một số A gọi là có bậc K đối với cơ số B nếu như :

A = Bx1 + Bx2 + … + Bxk

( trong đó x1 ¹ x2 ¹ x3 … ¹ xk )

Ví dụ :

17 có bậc 2 đối với cơ số 2 vì 17 = 24 + 20 .

151 có bậc 3 đối với cơ số 5 vì 151 = 53 + 52 + 50.

Yêu cầu : Cho trước 1 đoạn [X,Y] . Hãy xác định xem trong đoạn này có bao nhiêu số có bậc K đối với cơ số B.

Giới hạn : + 1 £ X £ Y £ 109.

+ 1 £ K £ 20, 2 £ B £ 9.

+ Bộ nhớ : 200KB.

+ Time limit : 1 s.

Input

X Y K B

Output

Gồm 1 số duy nhất là kết quả tìm được .

Ví dụ

Input

15 20 2 2

Output

3

( Giải thích : Đó là các số 17 = 24 + 20 .

18 = 24 + 21.

20 = 24 + 22. )



Thuật giải :

Ta sẽ đưa bài toán này về một bài toán nhỏ hơn đó là cho biết trong đoạn [1,A] có bao nhiêu số có bậc K đối với cơ số B.

Với mỗi giá trị A ta đều xác định được Bn sao cho Bn+1 > A . Áp dụng tính chất: Bn > Bn-1 + Bn-2 + … B0 ® A > Bn-1 + Bn-2 + … B0.

® Tổng bất kỳ của 1 tổ hợp K phần tử của (n-1) phần tử này cũng đều < A ( tức là : A > Bx1 + Bx2 + …+ Bxi +… + Bxk ( với mọi xi £ n–1 ) ).

® Như vậy ta đã giải quyết xong vấn đề với các số mà không chứa Bn, nếu như không chứa Bn thì số lượng số thoả mãn sẽ = Tổ hợp chập K của (n-1) . Ta sẽ tiếp tục giải quyết vấn đề với các số mà có dạng = Bn + Bx2+…+Bxk.Dễ thấy vấn đề ở đây lại quay về là tìm số lượng các số có bậc (K-1) đối với cơ số B trong đoạn [1,A-Bn] và không chứa Bn, vậy thì ở đây ta chỉ cần xác định lại n mà thôi, n(mới) £ n (cũ) – 1.

Như vậy bài toán đã được giải quyết. Nói tóm lại đây là một bài khá đặc trưng cho QHĐ = Đệ quy với công thức truy hồi đơn giản :

Cal(A,K,B) = Tổ hợp chập K của (N-1) + Cal(A-Bn,K-1,B).

Bài 2 : Nikifor – 2