[codeforces 55]D. Beautiful numbers

试题描述

Volodya is an odd boy and his taste is strange as well. It seems to him that a positive integer number is beautiful if and only if it is divisible by each of its nonzero digits. We will not argue with this and just count the quantity of beautiful numbers in given ranges.

输入

The first line of the input contains the number of cases t (1 ≤ t ≤ 10). Each of the next t lines contains two natural numbers li and ri(1 ≤ li ≤ ri ≤ 9 ·10¹⁸).

Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cin (also you may use %I64d).

输出

Output should contain t numbers — answers to the queries, one number per line — quantities of beautiful numbers in given intervals (from l_i to r_i, inclusively).

输入示例

2
1 9
12 15

输出示例

9
2

数据规模及约定

见“输入”

题解

“能同时被所有数位上的数字整除”等价于“能被所有数位上数字的最大公约数整除”。于是设 f[i][k][m] 表示一个 i 位的数，所有数字的最小公倍数等于 k，且这个数为 m。等等，状态 m 都知道这个数了，那 dp 个啥？别着急，我们一步步优化。

我们知道 lcm(1, 2, 3, 4, 5, 6, 7, 8, 9) = 2520（就是1~9的最小公倍数），那么对于刚才 m 的那一维状态是没有必要太大的，将这维状态对 2520 取个模就好了，即 m 表示这个数对 mod 2520 的值。

还有，1~9 这些数中，所有可能出现的最小公倍数只有 48 个（这个不妨读者自己写程序统计一下），所以离散一波 k 就变成最大只有 48 的数了。

最后状态数大概是：19 * 48 * 2520 = 2298240。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
#define LL long long

LL read() {
	LL x = 0, f = 1; char c = getchar();
	while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
	while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
	return x * f;
}

#define maxn 21
#define maxm 2521
#define maxc 49
int Lcm[maxc], cl, id[maxm], Gcd[maxm][maxm];
bool tmp[maxm];
LL f[maxn][maxc][maxm], ten[maxn];

int gcd(int x, int y){ return !y ? x : gcd(y, x % y); }

int get(int l, int x) {
	int nl;
	if(!x && !l) nl = 0;
	if(x && l) nl = l * x / Gcd[l][x];
	if(!x && l) nl = l;
	if(x && !l) nl = x;
	return nl;
}

int num[maxn];
LL sum(LL x) {
	int cnt = 0; LL tx = x;
	while(x) num[++cnt] = x % 10, x /= 10;
	LL ans = 0; int l = 1;
	for(int i = cnt; i; i--) {
		for(int j = 0; j < num[i]; j++) {
			int nl = get(l, j);
			for(int k = 0; k <= cl; k++) {
				int nnl = get(nl, Lcm[k]);
				LL t;
				if(i < cnt) t = (tx / ten[i] * ten[i] + ten[i-1] * j) % 2520;
				else t = ten[i-1] * j % 2520;
				for(int m = 0; m < maxm - 1; m += nnl) {
					int M = (m - t + 2520) % 2520; if(M < 0) continue;
					if(f[i-1][k][M]) ans += f[i-1][k][M];
				}
			}
		}
		l = get(l, num[i]);
	}
	if(tx % l == 0) ans++;
	return ans;
}

int main() {
	for(int i = 1; i < maxm; i++)
		for(int j = 1; j < maxm; j++) Gcd[i][j] = gcd(i, j);
	
	tmp[1] = 1;
	for(int j = 2; j <= 9; j++)
		for(int x = maxm - 1; x; x--)
			if(tmp[x]) tmp[x*j/Gcd[x][j]] = 1;
	for(int i = 1; i < maxm; i++)
		if(tmp[i]) Lcm[++cl] = i, id[i] = cl;
	
	ten[0] = 1;
	for(int i = 1; i < maxn; i++) ten[i] = ten[i-1] * 10;
	
	f[0][0][0] = 1;
	for(int j = 0; j <= 9; j++) f[1][id[j]][j] = 1;
	for(int i = 1; i < maxn - 1; i++)
		for(int k = 0; k <= cl; k++)
			for(int m = 0; m < maxm; m++) if(f[i][k][m]) {
				int l = Lcm[k];
				for(int x = 0; x <= 9; x++) {
					int nl = get(l, x);
					f[i+1][id[nl]][(ten[i]*x+m)%2520] += f[i][k][m];
				}
			}
	int T = read();
	while(T--) {
		LL l = read(), r = read();
		printf("%I64d
", sum(r) - sum(l - 1));
	}
	
	return 0;
}