N的阶乘的数学技巧

Posted on   |   In   |  

关于N的阶乘中的一些数学计算技巧

N的阶乘中末尾有几个0

分析:如果N的阶乘可以写成$K * 10^m$,并且K不能被10整除，那么(N!)末尾有m个0。其次，可以根据ugly number的分析，对N!进行质因数分解，$(N!) = 2^x * 3^y * 5^z$,所以m只能跟x和z相关，m = min{x, z}。x>=z,因为能被2整除的数出现的频率比能被5整除的数高得多，所以把公式可以简化为求n!中质因数5的个数

1
2
3
4
5
6
7
8
9
10
11
12
int numberOfFive(int N){
    int count= 0;
    
    for(int i = 1; i <= N; i++){
        int j = i;
        while(j % 5 == 0){
            count++;
            j /= 5;
        }
    }
    return count;
}

另一种方法:
N!中质因数5的个数为:
$[N/5] + [N/25] + [N/5^3]+...$

1
2
3
4
5
6
7
8
9
int numberOfFive2(int N){
    int count = 0;
    
    while(N){
        ret += N/5;
        N /= 5;
    }
    return count;
}

N的阶乘的二进制最低位1的位置

例如，给出N = 4，N! = 24(11000),返回的是4.
这个问题可以转化为求出N!含有质因数2的个数。答案为质因数2的个数加一。

1
2
3
4
5
6
7
8
9
int numberOfTwo(int N){
    int count = 0;
    
    while(N){
        N >>= 1;
        ret += N;
    }
    return count;
}

怎么能随机生成m个数，让其和等于n

题目: 假设生成26个非负随机数，要求其和是200，求程序生成此列数字。
解法一思路:把这道题想象成是将一根长200的绳子分割成26份，
1.初始化长度为27的数组

  1. a[0] = 0, a[26] = 200,其它位置随机填充0到200的值（不能重复）
  2. 对数组排序
  3. 相邻的数字相减，就是所要求的26个数字

解法二:因为非负，就是将1随机加到一个26位的数组中，随机200次。