题意：给定一个n。求区间[1, n]之间的全部的a的个数。a满足：

a能整除  把a表示自身二进制以后1的个数

思路：题意非常绕....

数位dp，对于全部可能的1的个数我们都dfs一次

对于某一个可能的1的个数p来说。状态dp(len, i, j, k)里的每一位分别表示当前位，当前确定位的值模除p，已经有了多少个1。是否已经小于给定的n。

注意的是这题范围非常大，要用unsigned long long 来定义n

#include<cstdio>

#include<cstring>

#include<cmath>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#include<vector>

#include<map>

#include<queue>

#include<stack>

#include<string>

#include<map>

#include<set>

#include<ctime>

#define eps 1e-6

#define ULL unsigned long long

#define LL  long long

#define pii (pair<int, int>)

//#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;

int digit[100];

ULL cnt_one;

ULL n;

LL d[100][100][100];

LL dfs(int len, ULL r, int k, int s) {

	if(!len) return (r==0&&k==cnt_one) ? 1:0;

	if(!s && d[len][r][k]!=-1) return d[len][r][k];

	LL ans = 0;

	ans += dfs(len-1, r, k, s&&!digit[len]);

	if(!(s&&!digit[len]) && k<cnt_one) ans += dfs(len-1, (r+(1ULL<<(len-1)))%cnt_one, k+1, s&&digit[len]);

	if(!s) d[len][r][k] = ans;

	return ans;

}

ULL solve(ULL n) {

	int cnt = 0, su = 0;

	while(n) {

		digit[++cnt] = n & 1;

		su++; n >>= 1;

	}

	LL ans = 0;

	for(cnt_one = 1; cnt_one <= su; cnt_one++) {

		memset(d, -1, sizeof(d));

		ans += dfs(cnt, 0, 0, 1);

	}

	return ans;

}

int main() {

	while(cin >> n) {

		cout << solve(n) << endl;

	}

    return 0;

}