求一个数阶乘末尾0的个数
#include<iostream>usingnamespacestd;//给定一个整数N,那么N的阶乘末尾有几个0?N=10,N!=3628800,末尾有2个0//1.如果我们从“哪些数相乘能得到10”这个角度来考虑,问题就变得简单了。//首先考虑,如果N!=K×10M,且K不能被10整除,那么N!末尾有M个0。再考虑//对N!进行质因数分解,N!=(2x)×(3y)×(5z)…,由于10=2×5,所以M只跟X和Z//相关,每一对2和5相乘可以得到一个10,于是M=min(X,Z)。不难看出X大于等于Z,//因为能被2整除的数出现的频率比能被5整除的数高得多,所以把公式简化为M=Z。//根据上面的分析,只要计算出Z的值,就可以得到N!末尾0的个数。//最直接的方法,就是计算i(i=1,2,…,N)的因式分解中5的指数,然后求和intcount1(intn){intret=0;intj=0;for(inti=1;i<=n;++i){j=i;while(j%5==0){++ret;j/=5;}}returnret;}//2.公式:Z=[N/5]+[N/52]+[N/53]+…(不用担心这会是一个无穷的运算,因为总存在一//个K,使得5K>N,[N/5K]=0。)//公式中,[N/5]表示不大于N的数中5的倍数贡献一个5,[N/52]表示不大于N的数中52//的倍数再贡献一个5intcount2(intn){intret=0;while(n){ret+=n/5;n/=5;}returnret;}intmain(){cout<<count1(10)<<endl;cout<<count2(10)<<endl;return0;}
#include<iostream>usingnamespacestd;//求N!的二进制表示中最低位1的位置给定一个整数N,求N!二进制表//示的最低位1在第几位?例如:给定N=3,N!=6,那么N!的二进制表示(1010)的最低//位1在第二位。//思路:判断最后一个二进制位是否为0,若为0,则将此二进制数右移一位,即为商值(为什//么);反之,若为1,则说明这个二进制数是奇数,无法被2整除(这又是为什么)。//所以,这个问题实际上等同于求N!含有质因数2的个数。即答案等于N!含有质因数//2的个数加1//由于N!中含有质因数2的个数,等于N/2+N/4+N/8+N/16+…1,intlowestOne(intN){intRet=1;//+最后的1while(N){N>>=1;Ret+=N;}returnRet;}//N!含有质因数2的个数,还等于N减去N的二进制表示中1的数目。我们还可以通过//这个规律来求解。intcount3(intv){intnum=0;while(v){v&=(v-1);++num;}returnnum;}intlowestOneCount(intN){returnN-count3(N)+1;}intmain(){cout<<lowestOne(3)<<endl;cout<<lowestOneCount(3)<<endl;return0;}
声明:本站所有文章资源内容,如无特殊说明或标注,均为采集网络资源。如若本站内容侵犯了原著者的合法权益,可联系本站删除。