hdu3652

#include <cstdio>
#include <cstring>
using namespace std;#define D(x) xconst int MAX_DIGIT = ;int n, m;
int f[MAX_DIGIT];
int memoize[MAX_DIGIT][][][][];void to_digits(int a)
{
for (int i = ; i < MAX_DIGIT; i++)
{
f[i] = a % ;
a /= ;
}
}int dfs(int digit, bool less, bool contain, bool one, int remain)
{
if (digit == -)
{
return contain && !remain;
}
if (memoize[digit][less][contain][one][remain] != -)
{
return memoize[digit][less][contain][one][remain];
}
int limit = less ? : f[digit];
int ret = ;
for (int i = ; i <= limit; i++)
{
int new_remain = (remain * + i) % ;
if (i == && one)
{
ret += dfs(digit - , less || i < f[digit], true, false, new_remain);
continue;
}
if (i == )
{
ret += dfs(digit - , less || i < f[digit], contain, true, new_remain);
continue;
}
ret += dfs(digit - , less || i < f[digit], contain, false, new_remain);
}
memoize[digit][less][contain][one][remain] = ret;
return ret;
}int main()
{
while (scanf("%d", &n) != EOF)
{
to_digits(n);
memset(memoize, -, sizeof(memoize));
int ans = dfs(, false, false, false, );
printf("%d\n", ans);
}
return ;
}