这题，没想出来，根本没想到用最小公倍数来更新，一直想状态压缩，不过余数什么的根本存不下，看的von学长的blog，比着写了写，就是模版改改，不过状态转移构造不出，怎么着，都做不出来。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define LL __int64
#define MOD 2520
LL dp[][][];
int index[];
int num[];
LL gcd(LL a,LL b)
{
return b == ?a:gcd(b,a%b);
}
LL lcm(LL a,LL b)
{
return a*b/gcd(a,b);
}
LL dfs(int pos,int pre,int mod,int bound)
{
int end,tpre,tmod,i;
LL ans = ;
if(pos == -)
return pre%mod == ;
if(!bound&&dp[pos][pre][index[mod]] != -)
return dp[pos][pre][index[mod]];
end = bound ? num[pos] : ;
for(i = ;i <= end;i ++)
{
tpre = (pre* + i)%MOD;
if(i)
tmod = lcm(mod,i);
else
tmod = mod;
ans += dfs(pos-,tpre,tmod,bound&&i == end);
}
if(!bound)
dp[pos][pre][index[mod]] = ans;
return ans;
}
LL judge(LL x)
{
int pos = ;
while(x)
{
num[pos++] = x%;
x = x/;
}
return dfs(pos-,,,);
}
int main()
{
int t,i,num = ;
LL x,y;
memset(dp,-,sizeof(dp));
for(i = ;i <= MOD;i ++)
{
if(MOD%i == )
index[i] = num++;
}
cin>>t;
while(t--)
{
cin>>x>>y;
printf("%I64d\n",judge(y)-judge(x-));
}
return ;
}