CF55D Beautiful numbers

题目链接

题意

定义一个数字\(x\)是\(beautiful\ number\)当且仅当\(x\)可以被其十进制表示下所有非\(0\)位置的数整除。

例如\(24\)是一个\(beautiful\ number\)，因为他可以被\(2\)和\(4\)整除。

而\(28\)不是一个\(beautiful\ number\)，因为他不能被\(8\)整除

给出两个数字\(L,R\; (1 \le L\le R \le 10^{18})\)

求出区间\([L,R]\)内有多少\(beautiful\ number\)

思路

首先显然的数位\(dp\)

先不考虑空间和时间问题

要让一个数字\(x\)整除所有数位上的数字。其实也就是要整除这些数字的最小公倍数\((lcm)\)。

用\(f[i][j][k]\)表示当前到了第\(i\)位，当前数字为\(j\;\) (先不管能否空间是否足够)。所选数字的\(lcm\)为\(k\)的方案数。

搜到最后看一下\(lcm\)是否整除\(j\)即可。

然后考虑空间问题。

在\(f[i][j][k]\)中，\(i\)是\(18\)左右，\(j\)是\(10^{18}\)，\(k\)最大是\(2520\)(\(2520\)是\(1\) ~ \(9\)的\(lcm\))

考虑优化一下\(j\)这一维。

显然所有可能的\(lcm\)都是\(2520\)的因数。

而比较显然的
\[x \% p = x \% kp % p\]

所以我们可以把\(j\)那一维的数以\(2520\)为模数\(hash\)一下。

然后优化\(k\)那一维。

枚举一下可以发现。\(1\)~\(9\)的所有可能组合中。\(lcm\)的种类其实只有\(50\)种左右。所以就可以把最后一维压成\(50\)左右

然后就可以愉快的数位\(dp\)啦！

代码

/*
* @Author: wxyww
* @Date:   2019-03-17 08:30:41
* @Last Modified time: 2019-03-17 19:36:46
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
const int LCM = 2520;
#define int ll
ll read() {
    ll x = 0, f = 1; char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
ll L, R;
int dy[100], pk[LCM + 100];
int get_lcm(int x, int y) {
    if (!y) return x;
    return x * y / __gcd(x, y);
}
namespace BF2 {
    int pos, f[20][3000][60], a[20];
    ll dp(ll p, ll now, ll lcm, int lim) {
        if (!p) return now % dy[lcm] == 0;
        if (f[p][now][lcm] != -1 && !lim) return f[p][now][lcm];
        int up = 9;
        if (lim) up = a[p];
        int tmp = 0;
        for (int i = 0; i <= up; ++i) 
            tmp += dp(p - 1, ((now * 10 + i) % LCM), pk[get_lcm(dy[lcm], i)], lim & i == up);
        if (!lim) f[p][now][lcm] = tmp;
        return tmp;
    }
    ll solve(ll x) {
        pos = 0;
        while (x) {
            a[++pos] = x % 10; x /= 10;
        }
        return dp(pos, 0, 1, 1);
    }
    void main() {
        cout << solve(R) - solve(L - 1) << endl;
    }
}
signed main() {
    int T = read();
    memset(BF2::f, -1, sizeof(BF2::f));
    int cnt = 0;
    for (int i = 1; i <= LCM; ++i) {
        if (LCM % i == 0) {
            dy[++cnt] = i; pk[i] = cnt;
        }
    }
    while (T--) {
        L = read(), R = read();
        BF2::main();
    }
    return 0;
}

CF55D Beautiful numbers

原文：https://www.cnblogs.com/wxyww/p/CF55D.html