一个很典型的数位统计，统计0-n中p进制下字符k出现了多少次。
最不会的题目就是数位统计了，每次写这种题都写得头晕。今天先是想学学数位dp的，但学了一下午还是不会……还是太弱了。
直到晚上还是用普通的统计方法写了，这题有一个奸诈之处就是k可能大于p……
真的弱爆了，现在啥都不会了，继续好好刷题，希望元旦之前可以推进到dp，每天至少一题
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <math.h>
using namespace std;
int main()
{
long long n;
int base,A,now;
char aim;
long long b[65]={0,1},c[65]={0,1},i;
while(~scanf("%lld%d%*c%c",&n,&base,&aim))
{
if(aim>='0'&&aim<='9')A=aim-'0';
else if(aim>='A'&&aim<='Z')A=aim-'A'+10;
else A=aim-'a'+36;
if(A==0&&n==0){printf("1\n");continue;}
if(A>=base){printf("0\n");continue;}
long long level,ans=0,now;
level=(1.0*log(n)/log(base))+1.0;
for(i=2;i<=level;i++)
{
b[i]=base*b[i-1];
c[i]=b[i]*i;
}
for(i=level;i>0;i--)
{
now=n/b[i];n%=b[i];
ans+=now*c[i-1];
if(now>A)ans+=b[i];
if(now==A)ans+=n+1;
}
if(A==0)
{
for(i=level;i>0;i--) ans-=b[i];
ans++;
}
printf("%lld\n",ans);
}
}