hdu 5179 beautiful number (数位DP考虑前导0)

beautiful number

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 902    Accepted Submission(s): 576

Problem Description

Let A=∑ni=1ai∗10n−i(1≤ai≤9)(n is the number of A's digits). We call A as “beautiful number” if and only if a[i]≥a[i+1] when 1≤i<n and a[i] mod a[j]=0 when 1≤i≤n,i<j≤n(Such as 931 is a "beautiful number" while 87 isn't).

Could you tell me the number of “beautiful number” in the interval [L,R](including L and R)?

Input

The fist line contains a single integer T(about 100), indicating the number of cases.

Each test case begins with two integers L,R(1≤L≤R≤109).

Output

For each case, output an integer means the number of “beautiful number”.

Sample Input

2 1 11 999999993 999999999

Sample Output

10 2

题意：

A：a1a2a3a4......an，如果满足ai>=ai+1，ai%aj==0  (i<j<=n)，则A称为完美数。

问在[L,R]内有多少这样的数

解析：

这一题数位条件只要满足ai>ai+1 && ai%ai+1==0

因为整除可以传递，b是a的因子，c是b的因子，则c是a的因子

limit只能表示用于是否达到给定数的边界！！

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long int ll;

int a[13];
ll dp[13][13];

ll dfs(int pos,int state,bool limit,bool lead)
{
    ll ans=0;
    if(pos==-1)
    {
        return 1;
    }

    if(!limit/*&&!lead*/&&dp[pos][state]!=-1) return dp[pos][state];

    int up=limit?a[pos]:9;     
    //if(!lead) up=min(up,state);   //这样错的原因是limit只能表示该次枚举数位有没有超a[pos]的界限
	                                //例如边界是55321，当万位遍历到4，千位遍历到4时，遍历到百位时limit=true，此时up=3(443..)
    for(int i=0;i<=up;i++)          //但此时正确的up=4（444..）,并没有遍历到边界
    {
		if(!lead&&i>state) continue; 
        if(!lead&&i==0) continue; 
        if(lead||state%i==0)
        {
            ans+=dfs(pos-1,i,limit&&i==up,lead&&i==0);
        }
    }

    if(!limit/*&&!lead*/) dp[pos][state]=ans;
    return ans;

}


ll solve(ll n)
{
    ll ans=0;
    int pos=0;
    while(n)
    {
        a[pos++]=n%10;
        n=n/10;
    }
    memset(dp,-1,sizeof(dp));
    ans+=dfs(pos-1,0,true,true);
    return ans;
}


int main()
{
    int t;
    ll l,r;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld%lld",&l,&r);
        printf("%lld\n",solve(r)-solve(l-1));
    }
}