1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
| # include<bits/stdc++.h>
using namespace std; typedef long long int LL; /********************************/
int num[20]; LL dp[20][8][2];
LL dfs(int pos,int mod,int limit,int status){ if(pos<0) return (status||mod%7==0); if(dp[pos][mod][status]!=-1&&!limit) return dp[pos][mod][status]; //忘写 limit 懵逼1000天有没有
int endi=9; if(limit) endi=num[pos];
LL res = 0; for(int i=0;i<=endi;i++) res+=dfs(pos-1,(mod*10+i)%7,limit&&i==endi,i==7||status);
if(!limit) dp[pos][mod][status] = res; return res; }
LL cal(LL x){ if(!x) return 0; int len=0; while(x) num[len++]=x%10,x/=10; return dfs(len-1,0,1,0)-1; }
void solve(LL x){ LL l=7,r=(1ll<<63)-1,mid,ans=-1; //r写成1e18 wa懵逼有没有,,,,
while(l<=r){ mid=((r-l)>>1)+l; LL tmp = cal(mid); tmp -= cal(tmp); if(tmp>=x)ans=mid,r=mid-1; else l=mid+1; } printf("%lld\n",ans); }
int main(){ // printf("%lld\n",~(1ll<<63)); memset(dp,-1,sizeof(dp)); LL n; while(~scanf("%lld",&n)) solve(n); return 0; }
|