排列数计算与亲和数判断的算法实现与优化

1. 排列数函数的实现与优化

排列数计算是组合数学中的基础问题，在实际编程竞赛和算法设计中经常出现。我们先来看一个经典的排列数计算实现方案。

1.1 基础阶乘实现

排列数公式为P(m,n) = m!/(m-n)!，因此我们需要先实现阶乘计算。以下是基础实现：

cpp复制long long fact(int n) {
    long long result = 1;
    for(int i = 1; i <= n; i++) {
        result *= i;
    }
    return result;
}

这个实现虽然简单，但有几点需要注意：

1. 使用long long类型防止整数溢出
2. 从1开始循环，避免0的阶乘问题
3. 时间复杂度为O(n)

注意：当n>20时，即使是long long也会溢出。在实际应用中需要考虑大数处理方案。

1.2 排列数计算的优化

直接计算两个阶乘再相除虽然直观，但存在效率问题和潜在的溢出风险。我们可以优化为：

cpp复制long long permutation(int m, int n) {
    if(m < n) return 0;
    long long result = 1;
    for(int i = m; i > m - n; i--) {
        result *= i;
    }
    return result;
}

这种实现：

1. 避免了计算完整的阶乘
2. 减少了乘法运算次数
3. 推迟了溢出发生的时间点（但仍需注意范围）

2. 亲和数判断的算法实现

亲和数是指两个数中，一个数的真约数之和等于另一个数。判断两个数是否为亲和数需要计算它们的真约数和。

2.1 真约数计算优化

cpp复制long long sum_proper_divisors(long long n) {
    if(n == 1) return 0;
    long long sum = 1;  // 1是所有大于1的数的真约数
    for(long long i = 2; i * i <= n; i++) {
        if(n % i == 0) {
            sum