[Description]
美丽数是指能被它的每一位非0的数字整除的正整数。
[Input]
包含若干组数据，每组数据一行两个数n,m，表示求[n,m]之间的美丽数的个数。
[output]
对于每组数据输出一个答案，各占一行。
Input
1
1 9
Output
9
Input
1
12 15
Output
2
[Hit]
0 < n , m < 10^18
测试数据不超过100组
基本思路是用：dp[len][mod][lcm]表示<=len的长度中，此数为mod,各数位的最小公倍数为lcm的数的个数来进行记忆化搜索。方法和上一题类似。
但我们发现，len在[1,20]范围内，mod在[1,1^18]范围内，lcm在[1,2520]范围内。所以dp数组肯定超内存。
下面我们来进行内存优化：
假设这个数为a,各个数位的值分别为ai,那么我们发现lcm(ai) | a.
而[1,9]的最小公倍数是2520.那么lcm(ai) | 2520, 所以lcm(ai) | (a%2520).
所以第二维大小我们可以从1^18降到2520,方法是%2520.
现在的dp数组的内存是20*2520*2520，还是很大。
然后我们再考虑：
我们发现某一个数的各个数位的数的最小公倍数最大是2520，而且只能是2520的公约数。而2520的公约数有48个。所以第三维我们只用[50]的空间就行了。
方法是用Hash进行离散化。‘
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long lol;
int bit[],ha[],len,cnt;
lol f[][][],ans;
int gcd(int x,int y)
{
if (!y) return x;
return gcd(y,x%y);
}
int lcm(int x,int y)
{
return x*y/gcd(x,y);
}
void has(int x,int l)
{
if (x>) return;
if (ha[l]==)
ha[l]=++cnt;
has(x+,lcm(l,x));
has(x+,l);
}
lol dfs(int pos,int pre_num,int pre_lcm,bool flag)
{int nxt_num,nxt_lcm,r,i;
lol s=;
if (pos==)
return pre_num%pre_lcm==;
if (flag&&f[pos][pre_num][ha[pre_lcm]]!=-)
return f[pos][pre_num][ha[pre_lcm]];
if (flag) r=;
else r=bit[pos];
for (i=;i<=r;i++)
{
nxt_num=pre_num*+i;
nxt_num%=;
if (i)
nxt_lcm=lcm(pre_lcm,i);
else nxt_lcm=pre_lcm;
s+=dfs(pos-,nxt_num,nxt_lcm,flag||(i<r));
}
if (flag)
f[pos][pre_num][ha[pre_lcm]]=s;
return s;
}
lol solve(lol x)
{
len=;
while (x)
{
len++;
bit[len]=x%;
x/=;
}
return dfs(len,,,);
}
int main()
{lol l,r;
int T;
cin>>T;
has(,);
memset(f,-,sizeof(f));
while (T--)
{
scanf("%I64d%I64d",&l,&r);
ans=solve(r)-solve(l-);
printf("%I64d\n",ans);
}
}