【アルゴリズム拾遺】階乗

転載は出典を明記してください.http://blog.csdn.net/ns_code/article/details/28335353
前言
    主に2つの階乗に関する問題を見て、そこからいくつかの法則を見ることができます.
タイトル1
    N!末尾0の個数
    末尾の0に現れる個数を探して、それでは私達は0を生む乗数を探して、つまりどの数が乗算して10を得ることができます.Nが必要だ!素因数分解を行い、10=2*5のため、0の個数はNになる!中2と5が現れる対数は関係しているが,2で割り切れる数が現れる頻度は5で割り切れる数よりずっと多いので,Nを見つけた.中素因数5の出現個数、すなわちN!末尾0の数.
    方法1
    最も直接的な方法は、1-Nの各数の因数分解の5つの数を計算し、加算します.コードは以下の通りです.

int FactorialNum0_1(int n)
{
	int count = 0;
	int i;
	for(i=1;i<=n;i++)
	{
		int j = i;
		while(j%5 == 0)
		{
			count++;
			j /= 5;
		}
	}
	return count;
}

    この方法の時間的複雑さはO(n)であった.
    方法2
    方法1では素因数5を含まない数も判断し,時間的複雑度が高い.
    2つ目の方法は、次の結論に従います.
    N!に含まれる素因数kの個数は、[N/k]+[N/k^2]+[N/k^3]+…(k^t>Nが常に存在するように、[N/k^t]=0)である
    この公式の証明は難しくなく,自分で理解してみると,[N/k]は1,2,3...Nの中でkで割り切れる数の個数に等しい.
    この方法で書かれたコードは以下の通りである.

int FactorialNum0_2(int n)
{
	int count = 0;
	while(n)
	{
		count += n/5;
		n /= 5;
	}
	return count;
}

    この方法の時間的複雑さはO(log 5 n)(ここでは5をベースとするnの対数)である.
タイトル2
    N!バイナリ表示で最下位ビット1の位置
    例えば3!は6で、バイナリは1010で、それでは最も低い位の1の位置は2で、ここで最も左の位置は1から計算を始めます.
    方法1
    最下位の1の位置をk位とするとN!=2^(k−1)+…+2^t+…+2^p+…,ここでt,p等は後のt+1位を意味し,p+1位も1であり,p>t>kである.これでわかりやすい、N!中素因数2の個数はk-1個、つまり最下位1の位置はN!中質因数2の個数に1を加えるので、問題はまたNを求めることに転化します!中質因数2の個数になりましたが、同様に結論を利用します.
N!に含まれる素因数kの個数は、[N/k]+[N/k^2]+[N/k^3]+…(k^t>Nが常に存在するように、[N/k^t]=0)である
    このように書かれたコードは次のとおりです.

int Lowest1(int n)
{
	int count = 0;
	while(n)
	{
		count += n/2;
		n /= 2;
	}
	return count + 1;
}

    この方法の時間的複雑さはO(log 2 n)である.
ここでは2をベースとしたnの対数である).
    方法2
    N!の中で素因数の2の個数を含んで、NからNの2進数の中で1の個数を減らすことに等しくて、どのようにNの2進数の中で1の個数を求めることについて、私のこの博文を参考にします;http://blog.csdn.net/ns_code/article/details/255425577、最も速い方法の操作ステップはバイナリの中の1の個数と等しいだけで、そのためこの方法の時間の複雑度はもっと良くて、方法はすでに速いが、この方法の時間の複雑度はO(k)で、その中でkはNです!で行ないます.この方法のコードはもう与えられない.