VOJ - SNAD

Source: SNAD
Tags: Dynamic Programming

Problem:
Tìm số lượng số có tích của chính nó với tổng các chữ số của nó nằm trong đoạn [X; Y].
T test < 21. 0 < X ≤ Y < 1e19.

Ví dụ:
Input:
1
20 30

Output:
2

Explanation:
2 số tìm được là 5 và 11.

Solution:
Đây là bài toán DP digits và ta sử dụng Đệ quy có nhớ để tính cho đơn giản.
Với mỗi tổng các chữ số là S, các số M tương ứng phải thỏa điều kiện (X - 1) / S < M ≤ Y / S. Với mỗi tổng S, ta đi tính DP[N][K][okL][okR], trong đó N là số thứ tự của chữ số đang xét, K là tổng đang xét, okL là số đang xét có lớn hơn hẳn (X - 1) / S chưa và okR là số đang xét có nhỏ hơn hẳn Y / S chưa. Tại mỗi cấu hình ta thử từng chữ số từ 0 → 9, nếu chữ số thỏa mãn thì chúng ta tìm cấu hình con để cộng vào, chi tiết công thức có thể coi ở phần code. Do S max chỉ có 171 nên độ phức tạp của chúng ta là hoàn toàn đủ.

Code:
#include <iostream>
#include <string.h>

using namespace std;

unsigned long long l, r, pow10[20], dp[20][170][2][2];
bool solved[20][170][2][2]; int s;

int digit(int i, unsigned long long x) {
    return int(x / pow10[i] % 10);
}

unsigned long long solve(int i, int k, bool okl, bool okr) {
    if (k > s) return 0;
    if (i < 0) return k == s;
    if (solved[i][k][okl][okr])
        return dp[i][k][okl][okr];
    solved[i][k][okl][okr] = true;
    unsigned long long res = 0;
    for (int d = 0; d <= 9; ++d)
        if ((okl || digit(i, l) <= d) && (d <= digit(i, r) || okr))
            res += solve(i - 1, k + d, okl || digit(i, l) < d, d < digit(i, r) || okr);
    return dp[i][k][okl][okr] = res;
}

int main() {
    pow10[0] = 1;
    for (int i = 1; i <= 19; ++i)
        pow10[i] = pow10[i - 1] * 10;
    int test; cin >> test;
    while (test--) {
        unsigned long long x, y, res = 0;
        cin >> x >> y;
        for (s = 1; s < 170; ++s)
            l = (x - 1) / s + 1, r = y / s,
            memset(solved, false, sizeof solved),
            res += solve(19, 0, 0, 0);
        cout << res << '\n';
    }
}