发现只要Σa[i]*i%Σa[i]==0就可以。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long t,l,r,dp[][][],bit[],ret=;
void get_bit(long long x)
{
ret=;
while (x) {bit[++ret]=x%;x/=;}
}
long long dfs(long long pos,long long val1,long long val2,bool flag)
{
if (!pos)
{
if (!val2) return ;
return val1%val2==;
}
if ((!flag) && (~dp[pos][val1][val2])) return dp[pos][val1][val2];
long long ans=,up=flag?bit[pos]:;
for (long long i=;i<=up;i++)
ans+=dfs(pos-,val1+i*pos,val2+i,flag&&i==up);
if (!flag) dp[pos][val1][val2]=ans;
return ans;
}
long long work(long long x)
{
if (x==-) return ;
get_bit(x);
return dfs(ret,,,);
}
int main()
{
scanf("%lld",&t);memset(dp,-,sizeof(dp));
for (long long i=;i<=t;i++)
{
scanf("%lld%lld",&l,&r);
printf("%lld\n",work(r)-work(l-));
}
return ;
}