编程之美

[编程之美_2.2]不要被阶乘吓到

题意要求计算n!的value值后面有0的个数，实际上可以理解为n!的计算中有多少个5的倍数被乘入。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

int CountZero(int n)
{
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        int tmp = i;
        while (0 == i % 5)
        {
            cnt++;
            tmp /= 5;
        }
    }
    return cnt;
}

题意求N!中二进制表示最低位1的位置，可以发现奇数的乘入对1的位置没有影响。一旦乘以2，整个数值为左移1位，故最后结果和分解因数后2的个数有关

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

int CountBinaryOne(int n)
{
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        int tmp = i;
        while (0 == tmp % 2)
        {
            cnt++;
            tmp /= 2;
        }
    }
    return cnt;
}