我认为关键是首先了解K值的模式及其增长速度。基本上，您有：
K(1) = 0K(X) = K(bitcount(X))+1 for X > 1
所以找到给定K的最小X值，我们看到
K(1) = 0K(2) = 1K(3) = 2K(7) = 3K(127) = 4K(170141183460469231731687303715884105727) = 5
因此，对于这样的示例来说
48238 10^18 9，答案是平凡的0。K=仅对1表示，而K =
1仅对2的幂表示，因此在关注范围内，我们几乎只会看到K值为2、3或4 ，再也看不到K> = 5
编辑
好的，因此我们正在寻找一种算法，可在LO..HI值范围内对K = 2,3,4的值进行计数，而无需在整个范围内进行迭代。因此，第一步是找到i =
1..59的bitcount（x）== i范围内的值数（因为我们只关心最大为10 ^ 18和10 ^ 18 <2 ^ 60的值）
。因此，将范围lo..hi分解为2个幂的子范围，它们的低n位不同-范围为x （2 ^ n）..（x + 1）（2 ^
n）-1。我们可以很容易地将arbitray lo..hi范围分解成这样的子范围。对于每个这样的子范围，将有带有i +
bitcount（x）个设置位的choice（n，i）值。因此，我们只需将所有子范围相加即可得到1..59的计数向量，然后对其进行迭代，将具有相同K值的那些元素相加即可得到答案。
编辑 （再次固定为与C89兼容并适用于lo = 1 / k = 0）
这是一个C程序，可以执行我之前描述的操作：
#include <stdio.h>#include <string.h>#include <assert.h>int bitcount(long long x) { int rv = 0; while(x) { rv++; x &= x-1; } return rv; }long long choose(long long m, long long n) { long long rv = 1; int i; for (i = 0; i < n; i++) { rv *= m-i; rv /= i+1; } return rv; }void bitcounts_p2range(long long *counts, long long base, int l2range) { int i; assert((base & ((1LL << l2range) - 1)) == 0); counts += bitcount(base); for (i = 0; i <= l2range; i++) counts[i] += choose(l2range, i); }void bitcounts_range(long long *counts, long long lo, long long hi) { int l2range = 0; while (lo + (1LL << l2range) - 1 <= hi) { if (lo & (1LL << l2range)) { bitcounts_p2range(counts, lo, l2range); lo += 1LL << l2range; } l2range++; } while (l2range >= 0) { if (lo + (1LL << l2range) - 1 <= hi) { bitcounts_p2range(counts, lo, l2range); lo += 1LL << l2range; } l2range--; } assert(lo == hi+1); }int K(int x) { int rv = 0; while(x > 1) { x = bitcount(x); rv++; } return rv; }int main() { long long counts[64]; long long lo, hi, total; int i, k; while (scanf("%lld%lld%d", &lo, &hi, &k) == 3) { if (lo < 1 || lo > hi || k < 0) break; if (lo == 0 || hi == 0 || k == 0) break; total = 0; if (lo == 1) { lo++; if (k == 0) total++; } memset(counts, 0, sizeof(counts)); bitcounts_range(counts, lo, hi); for (i = 1; i < 64; i++) if (K(i)+1 == k) total += counts[i]; printf("%lldn", total); } return 0; }对于2 ^ 63-1（LONGLONG_MAX）以下的值，它运行得很好。因为
48238 10000000000000000003它给出
513162479025364957，这似乎是合理的
编辑
给…的输入
48238 1000000000000000000 148238 1000000000000000000 248238 1000000000000000000 348238 1000000000000000000 4
给出的输出
4487878254941659920513162479025364957398959266032926842
这些加起来就是999999999999951763，这是正确的。k = 1的值是正确的（在2 ^ 16到2 ^
59范围内有44的2的幂）。因此，虽然我不确定其他3个值是否正确，但它们肯定是合理的。
