一、题意：找到第k（k上限1e12）大的，不包括4并且能被7整除的数。
题解：二分+数位dp。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN = 100;
LL dp[MAXN][7], digit[MAXN];
LL dfs(int pos, int mod, bool limit){
if (pos == -1){
return mod==0;
}
if (!limit && dp[pos][mod] != -1){
return dp[pos][mod];
}
int up = limit ? digit[pos] : 9;
LL ans = 0;
for (int i = 0; i <= up; ++i)
{
if (i == 4)continue;
int newmod = (mod * 10 + i) % 7;
LL tmp = dfs(pos - 1, newmod, limit && (i == up));
ans += tmp;
}
if (!limit)dp[pos][mod] = ans;
return ans;
}
LL solve(LL x){
memset(dp, -1, sizeof(dp));
int pos=0;
while(x){
digit[pos++]=x%10;
x/=10;
}
return dfs(pos-1, 0, true) - 1;
}
int main(){
LL k;
cin >> k;
LL l=1, r=1e18;
while(l<=r){
LL mid=(l+r)>>1;
LL tmp=solve(mid);
if(tmp<k)l=mid+1;
else r=mid-1;
}
cout<<l<<endl;
return 0;
}