Description:

$[L,R]$ 内有多少能被它自己的每一位数上的数整除的数。

多组数据。

$1\le T\le 10$

$1\le L\le R\le 9\times10^{18}$

Solution:

数位 $DP$ ，状态里加入当前选的数的最小公倍数 $curlcm$ ，把 $curlcm$ 离散化一下， $1\dots 9$ 的最小公倍数是 $2520$ ，所以 $sum\%2520$ 对结果没影响，还发现多组数据中 $f$ 数组的值是相同的，算出来一次之后还能用，只在程序最开始 $memset$ 成 $-1$ 即可。

Code:

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

typedef long long ll;

int testcases;

ll l,r;

ll gcd(ll a,ll b){return (b == 0ll ? a : gcd(b,a % b));}

inline ll lcm(ll a,ll b){return a / gcd(a,b) * b;}

#define MAXL 22

int len,bit[MAXL];

int to[2521];

int tot = 0;

ll f[MAXL][2521][300];

inline int uni(int k){return (to[k] == 0 ? (to[k] = ++tot) : to[k]);}

ll dfs(int pos,int sum,int curlcm,bool bord)

{

	if(pos == 0)

	{

		if(sum % curlcm == 0)return 1;

		else return 0;

	}

	if(!bord && f[pos][sum][uni(curlcm)] != -1)return f[pos][sum][uni(curlcm)];

	int limit = (bord ? bit[pos] : 9);

	ll res = 0;

	for(int i = 0;i <= limit;++i)

	{

		res += dfs(pos - 1,(sum * 10 + i) % 2520,(i ? lcm(curlcm,i) : curlcm),bord && (i == limit));

	}

	if(!bord)f[pos][sum][uni(curlcm)] = res;

	return res;

}

inline ll calc(ll t)

{

	len = 0;

	memset(bit,0,sizeof(bit));

	while(t > 0)

	{

		bit[++len] = t % 10;

		t /= 10;

	}

	ll res = dfs(len,0,1,true);

	return res;

}

int main()

{

	memset(f,-1,sizeof(f));

	scanf("%d",&testcases);

	for(int i = 1;i <= testcases;++i)

	{

		cin >> l >> r;

		cout << calc(r) - calc(l - 1) << endl;

	}

	return 0;

}