VN_ZR_I - Số không (I)
Tác giả: khuc_tuan
Ngôn ngữ: C++
#include "stdio.h"
#include "string.h"
int n, k;
int a[40], b[40];
long long result;
long C[33][33];
void tinh(int i,int sk) {
for(int j=0;j<=i;++j) {
if(j+sk>0) result += C[j][i] * ((j+sk-1)/k+1);
}
}
void duyet(int i, int sk) {
if(i<0) {
if(sk>0) result += (sk-1)/k + 1;
return;
}
bool nhohon = false, lonhon = false;
for(int j=33;j>i;--j) {
if(a[j]>b[j]) {
nhohon = true;
break;
}
if(a[j]<b[j]) {
lonhon = true;
break;
}
}
if(nhohon) { tinh(i+1,sk); return; }
if(lonhon) return;
b[i] = 0;
duyet(i-1,sk+1);
if(a[i]==1) {
b[i] = 1;
duyet(i-1,sk);
}
}
void run() {
memset( a, 0, sizeof(a));
memset( b, 0, sizeof(b));
int last=-1;
for(int i=0;i<31;++i) if((n&(1<<i))!=0) { a[i] = 1; last = i; }
result = 0;
for(int i=last;i>=0;--i) {
memset( b, 0, sizeof(b));
b[i] = 1;
duyet(i-1,0);
}
printf("%lld\n",result);
}
void init() {
C[0][0] = 1;
for(int i=1;i<33;++i) {
C[0][i] = C[i][i] = 1;
for(int j=1;j<i;++j) C[j][i] = C[j-1][i-1] + C[j][i-1];
}
}
int main() {
init();
while(true) {
n = -11;
scanf("%d%d",&n,&k);
if(n==-11) break;
run();
}
}