1049 counting ones
时间: 2023-04-29 11:07:21 浏览: 68
题目简述:
给定一个整数n,你需要求出1到n这n个整数的二进制(binary)表示中数字1出现的次数。例如,对于n=3,1到3这3个整数的二进制表示分别是:1, 10, 11,其中1出现的次数为2次。因此,输出2即可。
题目思路:
这道题可以用暴力求解法:枚举1到n的每个整数,然后统计对应的二进制表示中1的个数即可。但此种做法不适用于大数据。因此,我们需要寻找更为高效的算法。其中一种常见方法是用每一位的数字来计算。
例如,对于一个二进制数11010,我们可以从低到高,第一位统计在0~1范围内出现的次数,第二位统计在0~3范围内出现的次数,第三位在0~7范围内,第四位在0~15范围内,最后统计总体中的1的个数。因为,我们可以发现,对于n的第i位上的数字,它出现1的次数由(n / (i*10) * i)个1,除去i-1位之后,如果大于2,则还要加上i个1。再来看一个具体的例子,对于11010,第一位上有10种情况,0出现5次,1也出现5次,对于第二位,共有110, 101, 100, 011, 010, 001, 000七种情况,其中从00到01这两种情况中,每个数字都出现了两次1,因此一共出现了2*2=4次1。同样地,对于 101 和 011 这两种情况,也是如此。
因此,最终代码如下(基于C++):
#include <iostream>
using namespace std;
#define int long long//避免溢出
signed main(){
int n, ans;
cin >> n;
for(int l = 1, r; l <= n; l = r + 1){
int k = n / l;
r = n / k;
ans += (r - l + 1) * (k / 10);
int t = (k % 10) * l;
if(t >= l) ans += t - l + 1;
}
cout << ans << endl;
return 0;
}
注意:本题的数据范围比较大,因此需要使用int long long类型避免溢出。