G – B-number

 #include<stdio.h>
 #include<string.h>
 using namespace std;
 typedef long long ll; int a[];
 int dp[][][]; //pos:当前位置
 //mod：余数
 //have ：0：前一位不是1 1：前一位是1 2：有13
 ll dfs(int pos,int mod,int have,bool limit){
     if(pos==-) return mod ==  && have == ;
     if(!limit && dp[pos][mod][have] != -)
         return dp[pos][mod][have];//没有上限并且已被访问过
     int up = limit?a[pos]:;
     ll ans = ,i;
     for(i = ;i <= up;i++){
        int modx = (mod*+i)%;
        int havex = have;
        if(have ==  && i==) havex=;
        if(have ==  && i!=) havex=;
        if(have ==  && i == ) havex=;
        ans += dfs(pos-, modx, havex, limit && i == a[pos]);
     }
     if(!limit) dp[pos][mod][have] = ans;
     return ans;
 } ll solve(ll x){
     int pos=;
     while(x){
         a[pos++]=x%;
         x/=;
     }
     return dfs(pos-,,,true);
 }
 int main(){
     ll n;
     memset(dp,-,sizeof(dp));
     while(scanf("%lld",&n)!=EOF){
         ll ans = solve(n);
         printf("%lld\n",ans;
     }
     return ;
 }