题目描述
输入一个正整数m,请输出从0到m中每一个数字二进制数中含有1的个数的总和,由于数值较大结果需要模100000.
输入格式
一个m
输出格式
二进制数中含有1的个数的总和s
输入输出样例
输入
2
输出
2
输入
5
输出
7
说明/提示
样例说明
20%的数据 m<=500
50%的数据 m<=1000
70%的数据 m<=50000000
100%的数据 m<=100000000
内存限制500MB
知识点：
统计kk这个数在二进制的表示下有几个1，代码如下：
#include <iostream> using namespace std; int main() { int kk; cin>>kk; int
count= 0; while(kk) { kk = kk & (kk-1);//核心代码 count++; } cout<<count<<endl;
return 0; }
解题思路:
这种解法,有几个1就执行几次。
把一个整数减去1，再与原数字做按位与运算，会把原数二级制位中最右边的1变成0.那么一个整数二进制表示中有几个1，就可以进行几次这样的操作。
0111减去1变成0110，二者进行与运算变成0110，则把原数做右边的1变成0.循环往复直到全为0结束。
代码如下:
#include <iostream> using namespace std; int main() { int m; cin >> m; int
count= 0; for (int i = 0; i <= m; i++) { int c = i; while (c) { c = c & (c - 1);
count++; } count = count % 100000; } cout << count << endl; return 0; }
但是我们会发现，上面的代码在运算过程，会进行很多重复运算，我们明明可以对这些数字进行记忆化，在运算过程中，之前算过的数，我们就不要算了，所以我们可以用dp
代码如下：
#include <iostream> using namespace std; const int N = 100000010; const int MOD
= 100000; int dp[N]; int main() { int sum = 0; int m; cin >> m; dp[0] = 0; for (
int i = 1; i <= m; i++) { dp[i] = dp[i & (i - 1)] + 1; dp[i] %= MOD; sum += dp[i
]; sum %= MOD; } cout << sum << endl; return 0; }
今日推荐