题意：给定一个n和k，求所有小于等于n的数中k进制和-k进制的值相等的有多少个组合使得xk==x−kx_k==x_{-k}

xk=a0∗k0+a1∗k1+...+ar∗krx_k=a_{0}*k^0 + a_1*k^1 + ... + a_r*k^r

x−k=a0∗(−k)0+a1∗(−k)2+...+ar∗(−k)rx_{-k}= a_0*(-k)^0 + a_1*(-k)^2 + ... + a_r*(-k)^r

显然之后项数为奇或者幂为偶数的那些项相同才能使得k进制和-k进制都相同 也就是

对于n=a0∗k0+a1∗k1+a2∗k2+...+ar∗krn = a_0*k^0 + a_1*k^1 + a_2*k^2 + ... + a_r*k^r

有多少个x=b0∗k0+b1∗k1+b2∗k2+...+br∗krx =b_0*k^0 + b_1*k^1 + b_2*k^2 + ... + b_r*k^r

并且x≤nx \leq n
从最高位考虑，
1)若rr为奇数，并且ar>0a_r>0那么就是kr/2k^{r/2}，否则转2)
2)若rr为偶数，那么
1.考虑brb_r为[0,ar−1][0,a_r-1]的情况，一共有ar∗kar2−1a_r*k^{\frac{a_r}{2}-1}
2.考虑brb_r为ara_r的情况，就是这一位一定定下，求r−1r-1位种数，转1)

代码：

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
LL K,n,tk[100000],res[100000];
LL dfs(int bpos){
	if(bpos%2==0){
		if(res[bpos]) return tk[bpos/2];
		else return dfs(bpos-1);
	}
	return res[bpos]*tk[bpos/2]+dfs(bpos-1);
}
int main(){
	while(~scanf("%lld%lld",&n,&K)){
		tk[0]=1;
		for(int i=1;;i++){
			tk[i]=tk[i-1]*K;
			if(tk[i-1]*K>n)break;
		}
		LL tn=n;
		res[0]=0;
		while(tn>0){
			res[++res[0]]=tn%K;
			tn=tn/K;
		}
		//if(n==0)res[++res[0]]=0;
		//printf("res0:%lld\n",res[0]);
		//for(int i=res[0];i>=1;i--)printf("%lld ",res[i]);
		//puts("");
		printf("%lld\n",dfs(res[0]));
	}
	return 0;
}