HSFZ_NOI_DIGIT_DP G 题解

· · 题解

G - Beautiful numbers

题目网址：https://vjudge.net/contest/243352#problem/G

题目来源：CF 55D http://codeforces.com/problemset/problem/55/D

time limit per test 4 seconds

memory limit per test 256 megabytes

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.

Input

The first line of the input contains the number of cases t (1\le t\le 10). Each of the next t lines contains two natural numbers l_i and r_i (1\le l_i\le r_i\le 9\times 10^{18}).

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

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).

Examples

Input

1
1 9

Output

9

Input

1
12 15

Output

2

题目大意：对于一个正整数n，可以被其每一个数位上的数整除，即若n可以表示为\sum_{i=0}^{m}a_i\times 10^i (0\le a_i\le 9)，有\forall a_i,a_i|n，那么这个数被称为Beautiful~Number。现在，需要你求出区间里的Beautiful~Number的个数。

数位DP模板题。看到求区间内满足某种条件的个数的题目，首先想到的就是差分，将求区间[l,r]内满足条件的数的个数转化为求两个区间[1,r],[1,l-1]内满足条件的数的个数的差。

我们发现如果一个数能整除它的所有数位上的数，那么它一定能整除所有这些数位上的数的最小公倍数（性质1），而1到9的最小公倍数是2520，所有数可能形成的数位上所有数的最小公倍数一定是2520的因数。（性质2）以它的平方为时间复杂度可以接受。

我们定义f[i][j][k]表示剩下i位需要规划，这前i位模2520的余数是j，当前的前i位数的最小公倍数是k，满足这些条件的Beautiful~Number的个数。

由于性质1,如果最后的数能整除k，那么它一定能整除它各位数字的最小公倍数。由于性质2,所有可能出现的k都是2520的因数，借助这一性质，将j取模2520，若所得的结果整除k，那么原来的数也一定整除k。

由f的定义，我们可以写出状态转移方程

f[i][j][k]=\sum f[i-1][(j\times10+x)~mod~2520][lcm(k,x)]~~~[1\le x\le maxx]

在转移的过程中，需要注意前缀0的处理。

然而，我们发现f数组占用了18\times 2520\times2520=114307200的内存，很显然太大了。但是1到9中任取一些数作lcm，有很多值是根本取不到的，浪费了很多空间。我们预处理一下，最多只有48种可能，远远小于2520，建立映射的关系，将其中的一维压成50，大大减小了空间占用，使得空间变得可以接受。

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int maxn=20;
const int mod=2520;
int T,cur,a[mod+1];
ll l,r,f[20][mod+1][50];
vector<int>dim;
int gcd(int x,int y){return x%y?gcd(y,x%y):y;}
int lcm_(int x,int y){if(!y)return x;return x/gcd(x,y)*y;}
ll dfs(int x,int mode,int lcm,bool op)
{
    if(!x)return mode%lcm==0?1:0;
    if(!op&&f[x][mode][a[lcm]])return f[x][mode][a[lcm]];
    int maxx=op?dim[x]:9;ll ret=0;
    for(int i=0;i<=maxx;i++)ret+=dfs(x-1,(mode*10+i)%mod,lcm_(lcm,i),op&(i==maxx));
    if(!op)f[x][mode][a[lcm]]=ret;
    return ret;
}
ll solve(ll x)
{
    dim.clear();
    dim.push_back(-1);
    ll t=x;
    while(t)dim.push_back(t%10),t/=10;
    return dfs(dim.size()-1,0,1,1);
}
main()
{
    for(int i=1;i<=mod;i++)if(mod%i==0)a[i]=++cur;
    scanf("%d",&T);
    while(T--)scanf("%lld%lld",&l,&r),printf("%lld\n",solve(r)-solve(l-1));
    return 0;
}