# [ACM] ural 1057 Amount of degrees (数位统计）

2021年09月15日 阅读数：3

## 1057. Amount of Degrees

Time limit: 1.0 second
Memory limit: 64 MB
Create a code to determine the amount of integers, lying in the set [ X; Y] and being a sum of exactly K different integer degrees of  B.
Example. Let  X=15,  Y=20,  K=2,  B=2. By this example 3 numbers are the sum of exactly two integer degrees of number 2:
17 = 2 4+2 0,
18 = 2 4+2 1,
20 = 2 4+2 2.

### Input

The first line of input contains integers  X and  Y, separated with a space (1 ≤  X ≤  Y ≤ 2 31−1). The next two lines contain integers  K and  B (1 ≤  K ≤ 20; 2 ≤  B ≤ 10).

### Output

Output should contain a single integer — the amount of integers, lying between  X and  Y, being a sum of exactly  K different integer degrees of  B.

### Sample

input output
```15 20
2
2
```
```3
```
Problem Source: Rybinsk State Avia Academy

```#include <iostream>
#include <string.h>
using namespace std;
int X,Y,K,B;
int c[40][40];

void init()//组合数
{
c[0][0]=1;
for(int i=1;i<=31;i++)
{
c[i][0]=c[i-1][0];
for(int j=1;j<=i;++j)
c[i][j]=c[i-1][j]+c[i-1][j-1];
}
}

int change(int n)
{
int b[40];
int len=0;
while(n)
{
b[len++]=n%B;
n/=B;
}
int ans=0;
for(int i=len-1;i>=0;i--)
{
if(b[i]>1)
{
for(int j=i;j>=0;j--)
ans+=(1<<j);
break;
}
else
ans+=(b[i]<<i);
}
return ans;
}

int cal(int x,int k)
{
int tot=0,ans=0;
for(int i=31;i>0;i--)
{
if(x&(1<<i))//第i位为1（从0開始的）,那么后面还剩下i个数字,后面的第一个数字为0，从i-1个数字中随意挑k-tot个
{
++tot;
if(tot>k)
break;
x=x^(1<<i);//1变为0
}
if((1<<(i-1))<=x)
ans+=c[i-1][k-tot];
}
if(tot+x==k)//考虑x这个数自己
++ans;
return ans;
}

int main()
{
init();
while(cin>>X>>Y>>K>>B)
cout<<cal(change(Y),K)-cal(change(X-1),K)<<endl;
return 0;
}
```