[codeforces] Beautiful numbers

题目链接

---

大致题意:

统计区间[l,r]内的数能整除它所有位上的非零整数的个数

---

解题思路:

如果一个数能整除它所有位上的非零整数,那么它一定可以整除它所有位上非零整数的最小公倍数

因此我们需要参数prelcm,用来记录前面数的最小公倍数

但是我们不可能记录这个数字本事是多少,因为它太大了,我们需要把它缩小

通过计算可以知道1~9的最小公倍数是2520,假设数字x可以整除它的所有位上的非零整数

那么,x%lcm(a[i])=0

然后2520%lcm(a[i])=0,这是肯定的

所以x%2520%lcm(a[i])=0,也一定成立,这样我们就把很大的数缩小到了2520

定义状态方程:f[i] [prelcm] [yu] 表示到第i位,前面数字的最小公倍数是prelcm,余数是yu的满足条件的数字个数

但是prelcm<=2520 ,yu<=2520,又超内存

我们只能想办法把prelcm缩小范围

又通过计算可以知道,1~9组成的最小公倍数只有48个,那么我们就可以通过哈希的方式将2520缩小到50,完美!!

---

AC代码:

#include <bits/stdc++.h>using namespace std;typedef long long ll;
const int N = 20;int a[N], h[2520];
ll f[N][50][2520];ll gcd(ll a, ll b) {return b == 0 ? a : gcd(b % a, b);
}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;
}ll dfs(int pos, int limit, int prelcm, int yu) {if (!pos) return yu % prelcm == 0;if (!limit && f[pos][h[prelcm]][yu] != -1)return f[pos][h[prelcm]][yu];ll res = 0;int end = limit ? a[pos] : 9;for (int i = 0; i <= end; ++i)res += dfs(pos - 1, limit && i == end, i == 0 ? prelcm : lcm(prelcm, i), (yu * 10 + i) % 2520);if (!limit)f[pos][h[prelcm]][yu] = res;return res;
}ll dp(ll n) {int len = 0;while (n) {a[++len] = n % 10;n /= 10;}return dfs(len, 1, 1, 0);
}
int main(void)
{int cnt = 0;for (int i = 1; i <= 2520; ++i)if (2520 % i == 0) h[i] = ++cnt;int t; scanf("%d", &t);while (t--) {memset(f, -1, sizeof f);ll l, r; scanf("%lld %lld", &l, &r);printf("%lld\n", dp(r) - dp(l - 1));}return 0;
}