分析：举个例子就能发现：偶数位上的数都必须是0，奇数位上的数可以取0~k-1,这就是一个标准的数位dp了.

      这编译器......数组越界了竟然不报错.

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;typedef long long ll;ll n, k, shu[2000000], kk, f[200000];ll dfs(ll len, bool limit){    if (len == 0)        return 1;    if (!limit && f[len])        return f[len];    ll cnt = 0, maxx = (limit ? shu[len] : k - 1);        if (len % 2 != 0)    {        for (int i = 0; i <= maxx; i++)            cnt += dfs(len - 1, limit && i == maxx);        return limit ? cnt : f[len] = cnt;    }    else    {        cnt += dfs(len - 1, limit && maxx == 0);            return limit ? cnt : f[len] = cnt;    }    }ll solve(ll x){    while (x)    {        shu[++kk] = x % k;        x /= k;    }    return dfs(kk, true);}int main(){    scanf("%lld%lld", &n, &k);    printf("%lld\n", solve(n));    return 0;}