D. Beautiful numbers

题目链接：http://codeforces.com/problemset/problem/55/D

time limit per test

4 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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 l_i and r_i (1 ≤ l_i ≤ r_i ≤ 9 ·10¹⁸).

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 l_i to r_i, inclusively).

Examples

Input

1
1 9

Output

Input

1
12 15

Output

2

题目大意：输入n,m,问你区间[n,m]内有多少个数能被它的不为0的位数整除
首先讲一下这道题用到的东西：
看一下下面的证明
sum%(x*n)%x == sum%x;
证明：设sum ＝ k*x+b
    等号左边:
        sum%(x*n)%x -> (k*x+b)%(x*n)%x 
        将k转为ka*n + kb代入;
        (ka*n*x+kb*x+b)%(x*n)%x -> (kb*x+b)%x -> b%x -> b
    等号右边:
        b
左右相等，证明成立
接着看：
那么我们就可以用上式中的x*n对num进行取余，记录其取余后的值，显然，1～9的最小公倍数2520是最合理的x*n。 

  而在逐位统计时，可以直接由前面位取余后的值来得到包含新一位的新数字取余后的值。 

  例如 RX(R是已知前面位取余后的值)，那么Rx%2520 == (R*10+x)%2520。就不在此废话证了。 

  我们使用记忆化搜索。 

  **dfs(len, num, lcm, flag)  

  len表示迭代的长度， 

  num为截止当前位的数对2520取余后的值。 

  lcm为截止当前位的所有数的最小公倍数。 

  flag表示当前数是否可以任意取值(对取值上限进行判断)** 

  则可用dp[len][num][lcm]来对其进行记录。 

  但lcm按2520取值根本开不下，所以对lcm进行离散化，因为lcm一定可以整除2520，所以将1～2520可以整除2520的数进行标记即可，测试后发现只有48个，满足当前情况。
看代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<stdio.h>

#include<string.h>

#include<cmath>

#include<math.h>

#include<algorithm>

#include<set>

#include<queue>

#include<map>

typedef long long ll;

using namespace std;

const ll mod=1e9+;

const int maxn=1e8+;

const int maxk=+;

const int maxx=1e4+;

const ll maxa=;

#define INF 0x3f3f3f3f3f3f

ll a[],Hash[];

ll dp[][][];

ll gcd(ll n,ll m)

{

    return m?gcd(m,n%m):n;

}

ll dfs(ll pos,bool limit,ll sum,ll lcm)//sum是当前位数对2520取余后的值，lam是当前位的最小公倍数

{

    if(pos==-)

    {

        return sum%lcm==;

    }

    if(!limit&&dp[pos][Hash[lcm]][sum]!=-) return dp[pos][Hash[lcm]][sum];

    int up=limit?a[pos]:;

    ll ans=;

    for(int i=;i<=up;i++)

    {

        ans+=dfs(pos-,limit&&i==up,(sum*+i)%maxa,i?lcm*i/gcd(lcm,i):lcm);

    }

    if(!limit) dp[pos][Hash[lcm]][sum]=ans;

    return ans;

}

ll solve(ll n)

{

    ll p=;

    while(n)

    {

        a[p++]=n%;

        n/=;

    }

    return dfs(p-,,,);

}

int main()

{

    ios::sync_with_stdio(false);

    memset(Hash,,sizeof(Hash));

    int cnt=;

    for(int i=;i<=maxa;i++)

    {

        if(maxa%i==)

            Hash[i]=cnt++;

    }

    int t;

    memset(dp,-,sizeof(dp));

    cin>>t;

    while(t--)

    {

        ll n,m;

        cin>>n>>m;

        cout<<solve(m)-solve(n-)<<endl;

    }

    return ;

}

巴特西

D. Beautiful numbers

最新文章

热门文章