7 的意志（数字 dp）

链接：https://ac.nowcoder.com/acm/contest/221/G
来源：牛客网
 

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

定义一个序列a:7,77,777......,7777777(数字全为7的正整数，且长度可以无限大）
clearlove7需要从含有7的意志的数里获得力量，如果一个整数能被序列a中的任意一个数字整除，并且其数位之和为序列a中任意一个数字的倍数，那么这个数字就含有7的意志，现在给你一个范围[n,m]，问这个范围里有多少个数字含有7的意志。

 

输入描述:

多组输入，每行两个个整数n，m（1<=n<=m<=1e18)，如果输入为"0 0"，停止程序。

输出描述:

每一行输出含有7的意志的数的个数。

示例1

输入

1 7
1 100
1 1000
0 0

输出

1
3
21

说明

1到100中符合条件的数字为7，70，77

解析:

要求各位相加和是是7的倍数,该数是7的倍数

ac:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
typedef long long ll;

ll a[20];
ll dp[20][10][10];

ll dfs(ll pos,ll pre,ll sum,bool limit)
{
    if(pos == -1)
    {
        return (pre % 7 == 0 && sum % 7 == 0);
    }
    if(!limit && dp[pos][pre][sum] != -1)
        return dp[pos][pre][sum];
    ll up = limit ? a[pos] : 9;
    ll tmp = 0;
    for(ll i = 0;i <= up;i++)
    {
        tmp += dfs(pos-1 ,(pre*10 + i) % 7,(sum + i) % 7,limit && i == a[pos]);
    }
    if(!limit&&dp[pos][pre][sum] == -1)
        dp[pos][pre][sum] = tmp;
    return tmp;
}

ll solve(ll x)
{
    ll pos = 0;
    while(x)//把数位都分解出来
    {
        a[pos++] = x%10;
        x /= 10;
    }
    return dfs(pos-1,0,0,true);
}

int main()
{
    ll le,ri;
    while(~scanf("%lld%lld",&le,&ri)!=EOF)
    {
        if(le == 0&& ri == 0)
            break;
        memset(dp,-1,sizeof dp);
        printf("%lld\n",solve(ri) - solve(le - 1));
    }
    return 0;
}