首先观察：
2! = 2×1 = (2)10 = (10)2， 则第一个1是第2位，2!有1个质因数2
3! = 3×2×1 = (6)10 = (110)2， 则第一个1是第2位，3!有1个质因数2
4! = 4×3×2×1 = (24)10 = (11000)2， 则第一个1是第4位，4!有3个质因数2
5! = 5×4×3×2×1 = (120)10 = (1111000)2， 则第一个1是第4位，5!有3个质因数2
6! = 6×5×4×3×2×1 = (720)10 = (1011010000)2，则第一个1是第5位, 6!有4个质因数3
...
这时候规律就很明显了，就是有n个质因数2的话，就会在二进制形式下后面跟n个0，则所求答案就是n+1，即在n+1位上出现第一个1.
这时候一个很朴素的思路是，测试n!的每个因子的质因数2的个数，然后加起来就好了。
代码如下：
#include <iostream>
using namespace std; int main(){
long long n;
while(cin>>n){
long long res = ;
for(long long i=;i<=n;i++){
long long temp = i;
while(temp%==){
res++;
temp/=;
}
}
cout<<res<<endl;
} return ;
}
此时复杂度为O(nlnn). 提交显示超时。
如何改进呢？
在二进制的形式下，每一位都有1/0两种填充方式，由于计算的是n!,所以这种“填充”是连续的，也就是说在*****0的基础上除以2（即右移一位）得到的就是该位的质因数2 的个数，只需要将这个过程一直做下去直到右移到位数为0即可。
代码如下：
#include <iostream>
using namespace std; int main(){
int n;
long long ans;
while(scanf("%d",&n)!=EOF){
ans=;
while(n){
ans+=n>>;
n=n>>;
}
printf("%lld\n",ans+);
}
return ;
}
此时复杂度为O(lnn),可ac.