本文接上一篇研究生机试算法。在讨论完几个经典入门算法后，我们来开始系统地学习研究生机试算法。

最大公约数

当我们遇到诸如求最大公约数、最小公倍数之类的数学问题时，大多数人第一时间会想到暴力枚举求解，因为我们并没有系统地学习过这方面的数学知识。所以，当我们查阅资料，我们可以发现，使用欧几里得算法可以使算法更加高效。过程如下：

若a,b全为零，则它们的最大公约数不存在；若a、b其中之一为零，则它们的最大公约数为a、b中非零的那个；若a、b都不为零，则使新a=b;新b=a%b，然后重复该过程。

这就是我们要介绍的欧几里得算法，它改变了上文提到的枚举算法所需要的情况，将算法规模大大缩小。


package com.algorithm.math;

import java.util.Scanner;

/**
 * @author fzm
 * @date 2019-02-23
 */
public class GCD {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a, b;
        while (sc.hasNextInt()) {
            a = sc.nextInt();
            b = sc.nextInt();
            System.out.println(gcd(a, b));
            sc.nextLine();
        }
    }

    private static int gcd(int a, int b) {
        if (b == 0) return a;
        else {
            return gcd(b, a % b);
        }
    }
}

这就是求最大公约数的算法，同样也可以使用非递归形式。

最小公倍数

a、b的最小公倍数为a*b/k，k为a、b的最大公倍数，因此可以使用上述算法求解。

高精度整数

如果计算的数据大于int(long)所能表示的最大范围，那么我们需要使用高精度整数类BigInteger，它里面内置了四则运算的API，只要考前查阅即可。

分解质因数

顾名思义，对一个数x 分解质因数即确定素数$p_1p_2p_3$，使其满足 $x = p_1^ {e_1} * p_2 ^ {e_2} * … * p_3 ^ {e_3}$ ，在特定条件下我们还要确定$e_1、e_2$等幂指数。
我们来看一道求质因数的个数的题（2007年清华大学研究生机试题），要求我们求出一个正整数N的质因数的个数，（1<N<10^9）。

package com.algorithm.math;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @author fzm
 * @date 2019-02-23
 */
public class NumOfPrime {
    private static boolean[] mark = new boolean[31623];
    private static int[] prime = new int[31623];//定义一个sqrt(10^9)大小的数组，保存质数
    private static int primeSize = 0;

    public static void main(String[] args) throws IOException {
        init();
        String str;
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        while ((str = bf.readLine())!= null) {
            int n = Integer.parseInt(str);
            out(n);
        }
        bf.close();
    }

    private static void out(int n) {
//        List<Integer> res = new ArrayList<Integer>();
        int res = 0;
        for (int i = 0; i < primeSize; i++) {
            if (n % prime[i] == 0) {
                while (n % prime[i] == 0) {
                    res++;//每一个能整除的质数，都使结果+1
                    n /= prime[i];
                }
            }
            if (n == 1) break;
        }
        if (n != 1) res++;//如果在范围内的质数都不能除尽该数，则证明在该范围内还存在一个质因数

        System.out.println(res);
    }

    /**
     * 初始化质数数组
     */
    private static void init() {
        for (int i = 1; i <= 31622; i++) {
            mark[i] = false;
        }
        for (int i = 2; i <= 31622; i++) {
            if (mark[i]) continue;
            prime[primeSize++] = i;
            for (int j = i * i; j <= 31622; j += i) {
                mark[j] = true;
            }
        }
    }
}

组合数

关于n!的问题

n!表示n的阶乘，并且有n!=1 * 2 * 3 * … * n成立，我们讨论一下关于它的问题，求n!中有多少个质因子p。如果我们先求n!在按上述计算，那么数据可能非常大，根本无法计算出来，因此我们需要更快的解。
我们以10!为例，显然其中有因子2的个数为5，$2^2$的个数为2，$2^3$的个数为1，因此共有8个质因子2。仔细思考变可以发现此过程可以推广为n!中有$(\frac{n}{p}+\frac{n}{p^2}+\frac{n}{p^3}+…)$个质因子p，其中除法均为向下取整。于是便得到了O(logn)算法，代码如下：
1
2
3
4
5
6
7
8
int cal(int n, int p){
int ans = 0;
while(n){
ans += n / p;
n /= p;
}
return ans;
}
利用这个算法，可以很快计算出n!的末尾有多少个零，只要带入cal(n, 5)即可。

组合数的计算

组合数$C_n^m$是指从n个不同元素中选出m个元素的方案数（m≤n），其定义式为$C_n^m=\frac{n!}{m!(n-m)!}$，由三个整数的阶乘得到。通过定义可以知道，组合数满足$C_n^m=C_n^{n-m}$，且有$C_n^0=C_n^n=1$成立。本节讨论如下两个问题：
1. 如何计算$C_n^m$。
2. 如何计算${C_n^m}$%p。

第一个问题

方法一：定义法

通过定义式来算，先求阶乘，再除法，这样阶乘相当庞大，因此只能接受50以内的计算。

方法二：递推

我们可以得到组合数的递推公式：

$\begin{equation} C_n^m = C_{n-1}^m + C_{n-1}^{m-1} \end{equation}$

从直观上看，公式总是把n减一，而把m保持原样或减一，这样这个递推公式最终总可以把n和m变成相同或是让m变为0，而又有$C_n^0=C_n^n=1$,这正好可以作为递归边界。代码如下：

long long C(long long n, long long m){
    if(m == 0 || m == n) return 1;
    return C(n - 1, m) + C(n - 1, m - 1);
}

方法三：定义式变形

我们观察该式：

$\begin{equation} \begin{aligned} C_n^m&=\frac{n!}{m!(n-m)!} \\ &=\frac{(n-m+1)×(n-m+2)×…×(n-m+m)}{1×2×3×…×m}\\ &=\frac{\frac{\frac{(n-m+1)×(n-m+2)}{2}×…}{…}×(n-m+m)}{m} \end{aligned} \end{equation}$

这样，就可以写出相应的代码了，代码如下：

long long C(long long n, long long m){
    long long ans = 1;
    for(long long i = 1; i <= m; i++){
        ans = ans * (n - m + i) / i;
    }
    return ans;
}

第二个问题

方法一：递推取模

这种方法基于第一个问题的方法二，是最容易实现的一种。只要在原先的基础上适当的得房对p取模即可。

方法二：卢卡斯定理

如果p是素数，将m和n表示为p进制：

$\begin{equation} \begin{aligned} m &= m_kp^k+m_{k-1}p^{k-1}+...+m_0\\ n &= n_kp^k+n_{k-1}p^{k-1}+...+n_0 \end{aligned} \end{equation}$

那么卢卡斯定理告诉我们， $C_n^m=C_{n_k}^{m_k}×C_{n_{k-1}}^{m_{k-1}}×…×C_{n_0}^{m_0}(mod p)$ 成立。例如对$C_8^3 mod 5$来说，有

$\begin{equation} \begin{aligned} m&=3=0×5^1+3\\ n&=8=1×5^1+3 \end{aligned} \end{equation}$

于是有$C_8^3mod5=C_1^0×C_3^3mod5=1$。卢卡斯定理的证明不在此处，我们直接给出代码，并且为了看起来清晰，此处把p设为全局变量，不作为参数传来传去。

int Lucas(int n, int m){
    if(m == 0) return 1;
    return C(n % p, m % p) * Lucas(n / p, m / p) % p;
}

LightYears's Blog

研究生机试算法(二)