## Editorial for Số không (I)

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của flashmt

var n,num,k:longint;
d:array[0..65] of byte;
c:array[0..32,0..32] of longint;
sl:array[0..32] of int64;
re:int64;

procedure init;
var i:longint;
begin
fillchar(d,sizeof(d),0);
i:=0;
while n>0 do
begin
d[i]:=n mod 2;
n:=n div 2;
inc(i);
end;
num:=i;
end;

procedure ini;
var i,j:longint;
begin
fillchar(c,sizeof(c),0);
c[0,0]:=1;
for i:=1 to 32 do
begin
c[i,0]:=1;
c[i,i]:=1;
for j:=1 to i-1 do
c[i,j]:=c[i-1,j]+c[i-1,j-1];
end;
end;

procedure work(k:longint);
var i,num0,j:longint;
begin
fillchar(sl,sizeof(sl),0);
for i:=1 to num-1 do
for j:=1 to i-1 do
sl[j]:=sl[j]+c[i-1,j];
num0:=0;
for i:=num-2 downto 0 do
if d[i]=1 then
begin
for j:=0 to i do
sl[j+num0+1]:=sl[j+num0+1]+c[i,j];
end
else inc(num0);
num0:=0;
for i:=0 to num-1 do
if d[i]=0 then inc(num0);
inc(sl[num0]);
for i:=1 to 32 do
for j:=(i-1)*k+1 to i*k do
if j<=32 then
re:=re+sl[j]*i;
end;

begin
ini;
while not eof do
begin
readln(n,k);
if n=1 then
begin
writeln(0);
continue;
end;
init;
re:=0;
work(k);
writeln(re);
end;
end.


#### Code mẫu của happyboy99x

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

long long f[32][32][2][2];
int g[32][2][2];
int n;
int k;

int G(int bit, int smaller, int started) {
if (bit == -1) return started;
int &res = g[bit][smaller][started];
if (res != -1) return res;
res = G(bit - 1, smaller | (n >> bit & 1), started);
if (smaller == 1 || (n >> bit & 1) == 1) {
res += G(bit - 1, smaller, 1);
}
return res;
}

long long F(int bit, int fromLastZero, int smaller, int started) {
if (bit == -1) return 0;
long long &res = f[bit][fromLastZero][smaller][started];
if (res != -1) return res;
res = F(bit - 1, started == 1 ? (fromLastZero + 1) % k : 0, smaller | (n >> bit & 1), started)
+ (started == 1 && fromLastZero == 0 ? G(bit - 1, smaller | (n >> bit & 1), started) : 0);
if (smaller == 1 || (n >> bit & 1) == 1) {
res += F(bit - 1, fromLastZero, smaller, 1);
}
return res;
}

int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
while (cin >> n >> k) {
memset(f, -1, sizeof f);
memset(g, -1, sizeof g);
printf("%lld\n", F(31, 0, 0, 0));
}
return 0;
}


#### Code mẫu của RR

//Wishing myself a happy lunar new year with a lot of accept solutions
//Written by Pham Quang Vu
program VN_ZR_I;
const
inp='';
out='';
type
mang=array[1..50] of longint;
var
fi,fo:text;
n,k,nbit:longint;
bit:mang;
c:array[0..40,0..40] of int64;
procedure openfile;
begin
assign(fi,inp);reset(fi);
assign(fo,out);rewrite(fo);
end;
procedure getbit(x:longint;var c:mang;var top:longint);
begin
top:=0;
while x>0 do
begin
inc(top);
c[top]:= x and 1;
x:=x shr 1;
end;
end;
procedure init;
var
i,j:longint;
begin
for i:=0 to 34 do c[0,i]:=1;
for i:=1 to 34 do
begin
c[i,i]:=1;
for j:=i+1 to 34 do c[i,j]:=c[i,j-1]+c[i-1,j-1];
end;
end;
procedure solve;
var
count,i,j:longint;
result:int64;
begin
getbit(n,bit,nbit);
result:=0;
for i:=nbit-1 downto 1 do
for j:=1 to i-1 do
result:=result+c[j,i-1]*((j-1) div k+1);
count:=0;
for i:=nbit-1 downto 1 do
if bit[i]=1 then
begin
for j:=0 to i-1 do
result:=result+c[j,i-1]*((j+count) div k+1);
end
else inc(count);
if count>=1 then result:=result+(count-1) div k+1;
writeln(fo,result);
end;
procedure enter;
begin
init;
while not eof(fi) do
begin
readln(fi,n,k);
if (n=0) and (k=0) then exit;
solve;
end;
end;
procedure closefile;
begin
close(fi);
close(fo);
end;
begin
openfile;
enter;
closefile;
end.


#### Code mẫu của hieult

#include<cstdio>
#include<cmath>
#include<math.h>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<sstream>
#include<list>
#define fi first
#define se second
#define PB push_back
#define MP make_pair
#define ep 0.00001
#define oo 111111111
#define mod 790972
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
#define rep(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, x) memset(a, x, sizeof(a))
#define SZ(a) (int)(a.size())
#define maxn 505
//#define g 9.81
double const PI=4*atan(1.0);

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;
typedef long long ll;
int dx[] = {+1, 0, -1, 0};
int dy[] = {0, -1, 0, +1};

void OPEN(){
freopen("A.in","r",stdin);
freopen("A.out","w",stdout);
}

typedef long long ll;

#define modun 2

int num, a[100];
ll dp[33][2][2][33];
long long n, m;

ll go(int pos, int less, int zero, int cnt) {
if (pos < 0){
if(!cnt) return 0;
else return (cnt - 1)/ m + 1;
}

ll &ret = dp[pos][less][zero][cnt];
if (ret != -1) return ret;

// cout << pos << " " << less << " " << zero << " " << cnt << endl;

ret = 0;

int maxd = less ? 1 : a[pos];
for (int d = 0; d <= maxd; ++d) {
ret += go(pos - 1, less | (d < a[pos]), zero | d, cnt + (zero && (!d)));
}

return ret;
}

ll howmany(ll A) {
if (A <= 0) return 0;

num = 0;
while (A > 0) {
a[num++] = A & 1;
A >>= 1;
}

memset(dp, -1, sizeof(dp));
return go(num - 1, 0, 0, 0);
}

ll solve(ll A, ll B) {
if (A == 0) {
if (B == 0) return 1;
return howmany(B) + 1;
}
return howmany(B) - howmany(A - 1);
}

int main(){
//OPEN();
while(scanf("%lld %lld", &n, &m) > 0){
printf("%lld\n", howmany(n));
}
}


#### Code mẫu của ll931110

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>
typedef long long ll;
using namespace std;

int n,k;
int c[34][34];
int digit,d[34];

void getC()
{
memset(c,0,sizeof(c));
for (int i = 0; i <= 32; i++) c[0][i] = 1;
for (int j = 1; j <= 32; j++)
for (int i = 1; i <= 32; i++) c[i][j] = c[i - 1][j - 1] + c[i][j - 1];
};

ll rec(int pos,int p)
{
if (p < 0) return 0;
if (!pos) return (p == 0) ? 1 : 0;
if (d[pos] == 0) return (rec(pos - 1,p - 1));
else
{
ll tmp = rec(pos - 1,p);
if (p) tmp += c[p - 1][pos - 1];
//     cout << "answer: " << pos << ' ' << p << ' ' << tmp << endl;
return tmp;
};
};

ll calc(int x)
{
//x zeroes in the numbers
//   if (x != 2) return 0;
ll ret = 0;
for (int i = 2; i < digit; i++) ret += c[x][i - 1];
//   cout << ret << endl;
ret += rec(digit - 1,x);
return ret;
};

ll solve()
{
ll ret = 0;
digit = 0;  int tmp = n;
while (tmp)
{
d[++digit] = tmp % 2;  tmp /= 2;
};
for (int i = 1; i < digit; i++)
{
tmp = calc(i); //if (i == 2) cout << "query: " << i << ' ' << tmp << endl;
ret += 1LL * tmp * ((i + k - 1)/k);
};
return ret;
};

int main()
{
//    freopen("zr.in","r",stdin);
//    freopen("zr.ou","w",stdout);
getC();
while (cin >> n >> k) cout << solve() << endl;
};


#### Code mẫu của khuc_tuan

#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();
}
}


## Comments

Please read the guidelines before commenting.

There are no comments at the moment.