D 明七暗七 +数位dp+二分

转变一下题意可以变为求区间内所有满足含有7或者是7的倍数的数，第一个条件数位dp容易枚举，第二个条件需要记录好每位数对7取模的余数，如果余数为0即为倍数。如14，第一位数位10，对7取模的余数维3，第二位为4对7取模余数为4，两者之和对7取模余数为0，故为7的倍数。故可以直接数位dp求出0 - l区间满足的数。左端点为m，我们只二分需要找到一个右端点是得满足刚好为n个时即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5+5;
int dp[20][10][2];//第一维维当前为第几位数，第二维为每个位对7取模的余数之和，第三维判断是否含7
int a[20];
int Pow(int x,int y){
	int tot = 1;
	while(y){
		if(y&1) tot = tot*x;
		x = x*x;
		y>>=1;
	}
	return tot;
}


int dfs(int pos,int limit,int sum,int flag){
	if(pos==-1){
		if(flag ||sum%7==0){//满足含7或者是7的倍数即可
			return 1;
		}
		else return 0;
	}
	if(!limit && dp[pos][sum][flag]!=-1) return dp[pos][sum][flag];
	int up = limit?a[pos]:9;
	int ans = 0;
	for(int i = 0;i<=up;i++){
		int sum_ = (sum+(i*Pow(10,pos))%7)%7;//某位数对7取模的余数+前几位的余数
		int flag_ = flag|(i==7);
//		int num_ = num*10+i;
		ans+=dfs(pos-1,limit && up==i,sum_,flag_);
	}
	if(!limit) dp[pos][sum][flag] = ans;
	return ans;
}


int solve(int x){
	int pos = 0;
	while(x){
		
		a[pos] = x%10;
		x/=10;
		pos++;
	}
	return dfs(pos-1,1,0,0);
}


signed main(){
	cin>>m>>n;
	memset(dp,-1,sizeof(dp));
	int ans = solve(m);
	int l = m+1;
	int r = 4e12;//枚举最大右端点
	int  p =0;
	while(l<=r){
		int mid = l+r>>1;
		int num = solve(mid);
		if(num-ans>=n){
			p = mid;
			r = mid-1;
		}else{
			l = mid+1;
		}
	}
	
	cout<<p<<endl;
	
	return 0;
}