暴力代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
int lcm(int a, int b)
{
    return a / gcd(a, b) * b;
}
// 返回 0~x 中符合要求的数的数量
int len, d[15];
// 当前数字是 number，数位 lcm 是 lcm_now
int dfs(int now, bool limit, bool zero, int number, int lcm_now)
{
    if (now == 0)
        return number % lcm_now == 0;
    int up = limit ? d[now] : 9;
    int res = 0;
    for (int num = 0; num <= up; num++)
    {
        int lcm_nxt = lcm_now;
        if (num != 0)
            lcm_nxt = lcm(lcm_nxt, num);
        res += dfs(now - 1, limit && (num == d[now]), zero && num == 0,
                   number * 10 + num, lcm_nxt);
    }
    return res;
}
int cal(int x)
{
    len = 1;
    d[len] = x;
    while (d[len] >= 10)
    {
        d[len + 1] = d[len] / 10;
        d[len] = d[len] % 10;
        len++;
    }
    return dfs(len, true, true, 0, 1);
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t, A, B;
    cin >> t;
    while (t--)
    {
        cin >> A >> B;
        cout << cal(B) - cal(A - 1) << "\n";
    }
    return 0;
}

满分代码

直接记忆化显然不行，两个优化：

• number 只存不超过模了 lcm(1~9) 的余数
• lcm_now 情况数不多（少于 50 种），只存对应编号，这里我直接开了个 map 存编号。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int LCM19 = 2520;
int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
int lcm(int a, int b)
{
    return a / gcd(a, b) * b;
}
// lcm_now 可能性不多，分别编号
int tot = 0;
map<int, int> lcm_id;
// 返回 0~x 中符合要求的数的数量
int len, d[20];
// 当前数字是 number，数位 lcm 是 lcm_now，lcm_now 只有不超过 50 种
int f[20][LCM19 + 5][50];
int dfs(int now, bool limit, bool zero, int number, int lcm_now)
{
    if (now == 0)
        return number % lcm_now == 0;
    if (lcm_id[lcm_now] == 0)
        lcm_id[lcm_now] = ++tot;
    if (!limit && !zero && f[now][number][lcm_id[lcm_now]] != -1)
        return f[now][number][lcm_id[lcm_now]];
    int up = limit ? d[now] : 9;
    int res = 0;
    for (int num = 0; num <= up; num++)
    {
        int lcm_nxt = lcm_now;
        if (num != 0)
            lcm_nxt = lcm(lcm_nxt, num);
        res += dfs(now - 1, limit && (num == d[now]), zero && num == 0,
                   (number * 10 + num) % LCM19, lcm_nxt);
    }
    if (!limit && !zero)
        f[now][number][lcm_id[lcm_now]] = res;
    return res;
}
int cal(int x)
{
    len = 1;
    d[len] = x;
    while (d[len] >= 10)
    {
        d[len + 1] = d[len] / 10;
        d[len] = d[len] % 10;
        len++;
    }
    return dfs(len, true, true, 0, 1);
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    for (int i = 0; i <= 19; i++)
        for (int j = 0; j <= LCM19; j++)
            for (int k = 0; k < 50; k++)
                f[i][j][k] = -1;
    int t, A, B;
    cin >> t;
    while (t--)
    {
        cin >> A >> B;
        cout << cal(B) - cal(A - 1) << "\n";
    }
    return 0;
}