Beautiful numbers （数位dp）

Beautiful numbers （数位dp）

Volodya is an odd boy and his taste is strange as well. It seems to him that a positive integer number is beautiful

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

Example

Input

1 1 9

Output

9

Input

1 12 15

Output

2

题目大概：

找出n和m之间能被它的所有位数整除的数的数量。

思路：

所有的数位是1到9，最小公倍数是5 *7* 8* 9，是2520，开数组为数位，和，最小公倍数，分别对应dp【20】【2520】【2520】，但是超内存，所以利用hash，把最后的最小公倍数压缩在50以内，因为可能的最小公倍数是48个。

代码：

#include #include #include using namespace std;long long a[22];int hash[2522];long long dp[22][2522][50];int gcd(int a,int b){ if(a=2)q=q*i/gcd(q,i); sun+=dpp(pos-1,(sum*10+i)%2520,q,limit&&i==a[pos]); } if(!limit)dp[pos][sum][hash[b]]=sun; return sun;}long long go(long long x){ int pos=0; while(x) { a[pos++]=x%10; x/=10; } return dpp(pos-1,0,1,1);}int main(){ long long n,m,t; int j; memset(dp,-1,sizeof(dp)); for(int i=1,j=0;i<=2520;i++) { if(2520%i==0)hash[i]=j++; } scanf("%I64d",&t); while(t--) { scanf("%I64d%I64d",&n,&m); printf("%I64d\n",go(m)-go(n-1)); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。