VN_ZR_I - Số không (I)
Tác giả: hieult
Ngôn ngữ: C++
#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));
}
}