http://lightoj.com/volume_showproblem.php?problem=1068

https://toph.co/p/m-beautiful-numbers

Một số nguyên chia hết cho 3 thì tổng các chữ số của nó cũng chia hết cho 3. Ví dụ: \(3702\ \vdots 3\) và \(3 + 7 + 0 + 2\ = \ 12\ \vdots \ 3\). Tính chất này cũng đúng đối với số 9.

Trong bài toán này, chúng ta sẽ dùng tính chất đó cho các số nguyên khác.

Dữ liệu vào:

Ba số nguyên dương \(a,b\) và \(k\) \((1\ \leq \ a\ \leq \ b\ < \ 2^{31};0 < k\ < 10000)\).

Kết quả:

Số lượng số nguyên trong phạm vi từ \(a\) đến \(b\) mà chia hết cho \(k\), đồng thời tổng các chữ số của nó cũng chia hết cho \(k\).

Ví dụ:

Solution

Phân tích tham số:

Khi sinh đến chữ số \(i\), ta cần biết tổng các chữ số của nó và số dư của phần số đã sinh rồi khi chia cho \(k\). Như vậy, ta cần thêm 2 tham số:

• \(sum\): là tổng các chữ số đã sinh được. \((sum\ \leq \ 90)\)

• \(sodu\): là số dư của phần số đã sinh được chia cho \(k\).

Hàm đệ quy \(thu(i,\ gh,\ sum,\ sodu)\) với mảng lưu \(F\lbrack i\rbrack\lbrack sum\rbrack\lbrack sodu\rbrack\).

• Nếu \(i < 0\) thì

  • Nếu \(sum\ mod\ K\ = 0\) và \(sodu = 0\) thì trả về 1;

  • Ngược lại, trả về 0

• Nếu \(gh = false\) và \(F\lbrack i\rbrack\lbrack sum\rbrack\lbrack sodu\rbrack\ \geq \ 0\) thì trả về \(F\lbrack i\rbrack\lbrack sum\rbrack\lbrack sodu\rbrack\)

• \(kq = 0;\)

• \(maxc\ = \ (gh\ = \ = true\ ?\ a\lbrack i\rbrack\ :\ 9)\)

• Với mỗi \(c\) chạy từ 0 đến \(maxc\):

  • \(ghm\ = \ (gh = = true)\ AND\ (c = = maxc)\)

  • \(kq\ = \ kq\ + \ thu(i - 1,\ ghm\ ,\ sum + c,\ (10*sodu + c)\ mod\ K);\)

• Nếu \(gh = false\) thì gán \(F\lbrack i\rbrack\lbrack sum\rbrack\lbrack sodu\rbrack = kq\)

• Trả về kq;

Hàm G(x)

• Tách các chữ số của x;

• Trả về thu(n-1, true, 0,0);

Độ phức tạp: số trạng thái tối đa là 10 * 2 * 90 * K.