sdutoj 2609 A-Number and B-Number

http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2609

A-Number and B-Number

Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^_^

题目描述

Tom is very interested in number problem. Nowadays he is thinking of a problem about A-number and B-number.
A-number is a positive integer whose decimal form contains 7 or it can be divided by 7. We can write down the first 10 A-number ( a[i] is the ith A-number)
{a[1]=7,a[2]=14,a[3]=17,a[4]=21,a[5]=27,a[6]=28,a[7]=35,a[8]=37,a[9]=42,a[10]=47};
B-number is Sub-sequence of A-number which contains all A-number but a[k] ( that k is a A-number.) Like 35, is the 7th A-number and 7 is also an A-number so the 35 ( a[7] ) is not a B-number. We also can write down the first 10 B-number.

{b[1]=7,b[2]=14,b[3]=17,b[4]=21,b[5]=27,b[6]=28,b[7]=37,b[8]=42,b[9]=47,b[10]=49};
Now Given an integer N, please output the Nth B-number

输入

The input consists of multiple test cases.

For each test case, there will be a positive integer N as the description.

输出

For each test case, output an integer indicating the Nth B-number.

You can assume the result will be no more then 2^63-1.

示例输入

示例输出

提示

来源

2013年山东省第四届ACM大学生程序设计竞赛

示例程序

分析：

一开始想到打表，结果超时咯，后来看了标程用了搜索写的，，，orz

超时代码：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 using namespace std;

 bool fun(int n){

     if(n%==) return true;

     while(n) {

         if(n%==) return true;

         n/=;

     }

     return false;

 }

 long long a[];

 long long  b[];

 int main(){

     int i,c=,cc=;

     //freopen("in.txt","r",stdin);

     for(i=;i<=;i++)

       if(fun(i)) a[++c]=i;

     for(i=;i<c;i++)

        if(!fun(i))

          { b[++cc]=a[i];}

     long long  n;

     while(cin>>n){

         if(n>cc-) cout<<"??";

         else

         cout<<b[n]<<endl;}

     return ;

 }

官方标程：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 using namespace std;

 #define ULL unsigned long long

 const ULL Maxn=((1uLL<<64uLL)-);

 ULL dp[][][];

 int digit[];

 ULL dfs(int pos,int pre,int flag,bool limit){

     if(pos==-) return flag||pre==;

     if(!limit&&dp[pos][pre][flag] != -) return dp[pos][pre][flag];

     int end = limit?digit[pos]:;

     int fflag,ppre;

     ULL ans=;

     for(int i = ;i <= end;i++){

         fflag = (i==)||flag;

         ppre=(pre*+i)%;

         ans+=dfs(pos-,ppre,fflag,limit&&i==end);

     }

     if(!limit) dp[pos][pre][flag]=ans;

     return ans;

 }

 ULL solve(ULL n){//找到n以下有几个A-number

     int pos = ;

     while(n){

         digit[pos++] = n%;

         n /= ;

         if(!n) break;

     }

     return dfs(pos-,,,)-;

 }

 ULL find(ULL n){//找到n以下有几个B-number

     ULL t = solve(n);//表示n包括n以下在A中有t个

     ULL tt = t - solve(t);//表示t(包括第t个)个A_number中有几个是符合在B中的，一直找到tt刚好等于n为止

     return tt;

 }

 int main()

 {

     memset(dp,-,sizeof(dp));

     ULL n;

     while(cin>>n){

             ULL l = , r= Maxn,mid;

             while(l <= r){

                 mid = ((r-l)>>)+l;

                 if(find(mid)<n) l = mid+;

                 else r = mid-;

             }

             ULL ans = r+;

             cout<<ans<<endl;

     }

     return ;

 }

巴特西