李老师买了一本有亲和数的数学书

某一天，李老师买了一本趣味数学书，上面提到了一种数——亲和数，所谓亲和数就是：定义数对 ( , )(x,y) 为亲和数对当且仅当 x、 y为不同正整数，且 x、 y各自的所有非自身正因子之和等于另一个数。例如 (220,284)(220,284) 和 (284,220)(284,220) 都是亲和数对，因为：220220的所有非自身正因子之和为：1+2+4+5+10+11+20+22+44+55+110=2841+2+4+5+10+11+20+22+44+55+110=284，284284的所有非自身正因子之和为：1+2+4+71+142=2201+2+4+71+142=220。数对（ , ）（x,y）跟（ , ）（y,x）被认为是同一数对，所以我们只考虑 < x<y 的情况。任务：李对某个范围内的亲和数对的数量非常感兴趣，所以希望你能帮他编写一个程序计算给定范围内的亲和数对的数量。给定一个范围 A到 B，如果 ≤ ≤ A≤x≤B，则我们称（ , ）（x,y）在范围[ , ][A,B]内。Input第一行两个正整数 A和 B。Output只有一行，就是[ , ][A,B]内亲和数对的数量。Sample Input200 1200Sample Output2Sample Explanation[200,1200][200,1200] 内的数对只有两个，分别是（220,284）（220,284）和（1184,1210）（1184,1210）。Hint100%100%数据：

你的题目出错了吧
1210不在200-1200范围内

#include <iostream>
using namespace std;
int FactSum(int n)
{
    int sum = 0;
    for (int i = 1; i < n; i++)
    {
        if (n % i == 0) sum += i;
    }
    return sum;
}
int main()
{
    int a, b;
    cin >> a >> b;
    int cnt = 0;
    for (int i = a; i <= b; i++)
    {
        int fs = FactSum(i);
        if (fs > i && fs <= b && FactSum(fs) == i) 
        {
            cnt++;
            //cout << i << " " << fs << endl;
        }
    }
    cout << cnt;
    return 0;
}

代码：

#include <iostream>
#include <algorithm>
using namespace std;

//求因子和
int cal(int n)
{
    int total = 0;
    for (int i = 1; i < n; i++)
    {
        if (n % i == 0)
            total += i;
    }
    return total;
}

int main()
{
    int a, b;
    int cnt = 0;
    cin >> a >> b;
    for (int i = a; i <= b; i++)
    {
        int t = cal(i);
        int t2 = cal(t);
        if (t2 == i && i < t)
            cnt++;
    }
    cout << cnt;
    return 0;
}

亲和数是指两个正整数 A 和 B，其中 A 的所有真因数之和等于 B，且 B 的所有真因数之和等于 A。以下是示例：

#include <iostream>
#include <vector>

using namespace std;

// 计算一个数的所有真因数之和
int sumOfProperDivisors(int num) {
    int sum = 1;  // 1 是所有正整数的真因数
    for (int i = 2; i * i <= num; ++i) {
        if (num % i == 0) {
            sum += i;
            if (i != num / i) {
                sum += num / i;
            }
        }
    }
    return sum;
}

int main() {
    int A, B;
    cout << "Enter the range A and B: ";
    cin >> A >> B;

    int count = 0;

    for (int num = A; num <= B; ++num) {
        int sumA = sumOfProperDivisors(num);
        if (sumA > num && sumA <= B) {  // Avoid counting pairs twice and check if sumA is within the range
            int sumB = sumOfProperDivisors(sumA);
            if (sumB == num) {
                cout << "Pair: (" << num << ", " << sumA << ")" << endl;
                count++;
            }
        }
    }

    cout << "Number of amicable pairs: " << count << endl;

    return 0;
}

【以下回答由 GPT 生成】

思路

1. 首先，我们需要一个函数来计算一个数的所有非自身因子之和。
2. 接着，我们需要遍历给定范围内的所有正整数，找到它们的非自身因子之和等于另一个数的情况。比如，对于数x，我们需要找到另一个数y，使得x的非自身因子之和等于y，同时y的非自身因子之和等于x。
3. 对于每一个数x，我们可以使用循环遍历范围内的数来查找与它匹配的数y。如果找到了匹配的数y，则我们找到了一个亲和数对。
4. 最后，我们统计找到的亲和数对的数量即可。

代码实现

def sum_factors(n):
    """
    计算一个数的所有非自身因子之和
    """
    factors = []
    for i in range(1, n//2+1):
        if n % i == 0:
            factors.append(i)
    return sum(factors)

def count_amicable_pairs(A, B):
    """
    计算给定范围内的亲和数对的数量
    """
    count = 0
    for x in range(A, B+1):
        y = sum_factors(x)
        if y > x and sum_factors(y) == x:
            count += 1
    return count

A, B = map(int, input().split())
result = count_amicable_pairs(A, B)
print(result)

复杂度分析

• 对于每个数x，计算其非自身因子之和的时间复杂度为O(x)。
• 对于给定范围内的每个数，我们需要计算其非自身因子之和，并比较与其他数是否匹配，因此总的时间复杂度为O((B-A)x).
• 空间复杂度为O(1)。

【相关推荐】

• 这个问题的回答你可以参考下: https://ask.csdn.net/questions/7475405