Codeforces-55D Beautiful numbers

http://codeforces.com/problemset/problem/55/D

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 ≤ t ≤ 10). Each of the next t lines contains two natural numbers li and ri (1 ≤ li ≤ ri ≤ 9 ·1018).

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 li to ri, inclusively).

题意：求区间美丽数的个数。所谓美丽数，是指一个数可以被它的每一位数字整除。

思路：因为num可以被它的每一位整除，等价于num可以被其每一位的lcm整除。

但是，状态不能设为（第pos位，以前每位的lcm），举个例子，num1=32，num2=312，假如按刚刚的状态跑到最后'2'那一位时，当前lcm都是3，但是312%6==0，而32%6!=0。

即算是不是美丽数，必须由整个num%lcm(每一位)。

由于x%b==x%(k*b)%b，lcm（1~9）=2520，num%lcm=num%2520%lcm

状态设为（第pos位，以前数%2520的值，当前lcm）

但是这个状态有18*2525*2520，空间开不下，因为1~9任意组合的lcm是离散的，只有48种组合，最后一维可以离散化一下。

参考这篇https://blog.csdn.net/qq_33184171/article/details/52332586

#include<bits/stdc++.h>
using namespace std;
#define ll unsigned long long

ll T,A,B;
ll a[20],dp[20][2600][50];
ll lcm_id[2530];

ll Lcm(ll a,ll b)
{
	if(!b)return a;
	return a/__gcd(a,b)*b;
}

ll dfs(ll pos,ll mod,ll lcm,bool limit)
{
	if(pos==-1)return mod%lcm==0;
	if(!limit&&dp[pos][mod][lcm_id[lcm]]!=-1)return dp[pos][mod][lcm_id[lcm]];
	int up= (limit?a[pos]:9);
	ll ans=0;
	for(int i=0;i<=up;i++)
	{
		ans+=dfs(pos-1,(mod*10+i)%2520,Lcm(lcm,i),limit&&i==a[pos]);
	}
	if(!limit)dp[pos][mod][lcm_id[lcm]]=ans;
	return ans;
}

ll solve(ll n)
{
	int pos=0;
	while(n)
	{
		a[pos++]=n%10;
		n/=10;
	}
	return dfs(pos-1,0,1,1);
}

void init()
{
	int idx=0;
	bool vis[2530]={0};
	for(int i=1;i<(1<<9);i++)
	{
		int ret=1;
		for(int j=0;j<9;j++)if((1<<j)&i)ret=Lcm(ret,j+1);
		if(!vis[ret])
		{
			vis[ret]=1;
			lcm_id[ret]=++idx;
		}
	}
}

int main()
{
//	freopen("input.in","r",stdin);
	memset(dp,-1,sizeof(dp));
	init();
	cin>>T;
	while(T--)
	{
		cin>>A>>B;
		cout<<solve(B)-solve(A-1)<<endl;
	}
	return 0;
}