题目链接：https://ac.nowcoder.com/acm/problem/17867

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

题目描述：

今天是个特殊的日子，CSL和他的小伙伴们围坐在一张桌子上玩起了明七暗七的游戏。游戏规则是这样的：

一个人报出一个起始数，接下来按照逆时针的顺序轮流报数，如果碰到数是7的倍数或含有7，则拍手，下一个人接着报数。直到有一个人报错了数字或者没有及时拍手为止。

玩游戏嘛，当然得有惩罚。这么简单的游戏对CSL的学霸小伙伴而言实在是太无脑了，轻轻松松数到上万根本不在话下。但是对于数学是体育老师教的CSL来说，实在是太难了。快帮他算算什么时候应该拍手吧。

题目思路：

题目总体思路：数位DP+二分查找。

数位DP：题目要求找到m以后第n个满足要求的数（被7整除或含有7）。满足要求的数我们可以将其逆向思维处理，比如1-7中，含有7或者被7整除的个数为1，即为7。也可以看作7个数中减去了不含有7或者被7整除的个数：7-1。数位DP，处理后者更为简单，所以可得：x中，满足题意的数有：x-solve(x)。dp[cur][sta]，sta可以用作处理%7后的状态。以上为数位DP的处理。

二分查找：为了寻找m后的第n个满足要求的数，可以用二分查找，即通过mid-solve（mid）和m-solve（m）关于n的关系进行比较，最后输出查找结果即可。

#include<bits/stdc++.h>  
#define INF 1e18  
#define inf 1e9  
#define min(a,b) a<b?a:b  
#define max(a,b) a>b?a:b  
#define lson l,m,rt<<1  
#define rson m+1,r,rt<<1|1  
#define IOS ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)  
using namespace std ;  
typedef long long ll;  
typedef unsigned long long ull;  
const ll mod = 1e9+7;  
 
int num[100];  
ll dp[100][10];  
ll dfs(int cur,int sta,bool limit){  
    if(cur == -1) return sta?1:0;  
    if(!limit && dp[cur][sta] != -1) return dp[cur][sta];  
    int up = limit?num[cur]:9;  
    ll cnt = 0;  
    for(int i = 0 ; i < up+1 ; i++){  
        if(i == 7) continue;  
        cnt += dfs(cur-1,(sta*10+i)%7,limit && i==up);  
    }  
    if(!limit) dp[cur][sta] = cnt;  
    return cnt;  
}  
ll solve(ll n){  
    int len = 0;  
    while(n){  
        num[len++] = n%10;  
        n /= 10;  
    }  
    return dfs(len-1,0,true);  
}  
int main(){  
    IOS;  
    ll n,m;  
    while(cin>>m>>n){  
        memset(dp,-1,sizeof(dp));  
        ll l = m+1,r = 1e13;  
        ll cnt = m - solve(m),mid,ans;  
        while(l<=r){  
            mid = (l+r)>>1;  
            if(mid-solve(mid)-cnt>=n) r = mid-1,ans = mid;  
            else l = mid+1;  
        }  
        cout<<ans<<endl;      
    }  
    return 0;  
}