【2029】亲和数对

Time Limit: 3 second
Memory Limit: 2 MB

【问题描述】

    某一天，tenshi看了一本趣味数学书，上面提到了亲和数：定义数对(x,y)为亲和数对当且仅仅当x、y为不同
正整数，且x、y各自的所有非自身正因子之和等于另一个数。
    例如 (220,284)是亲和数对，因为： 
    220的所有非自身正因子之和为：1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284 
    284的所有非自身正因子之和为：1 + 2 + 4 + 71 + 142 = 220 

    数对 (x,y) 跟 (y,x) 被认为是同一数对，所以我们只考虑x, tenshi对某个范围内的亲和数对的数量非常感
兴趣，所以希望你能帮她编写一个程序计算给定范围内的亲和数对的数量。给定一个范围A到B，如果A≤x≤B，则
我们称 (x,y)在范围[A,B]内的亲和数对。

【输入】

从输入文件第一行分别读入正整数A和B，其中A、B满足1 ≤ A ≤ B ≤ 10⁸ 且 B-A ≤ 10⁵

【输出】

输出文件只有一行，就是[A,B]内亲和数对的数量

【输入样例】

200 250

【输出样例】

【题解】

按照题目的要求，可以做一个函数专门用来计算某个数的所有因数之和。计算量会很大，但是题目真正的数据给的很小。所以能过。

因为重复的不算，还要判重。不过已知的亲和数对并不多，所以没差。

【代码】

#include <cstdio>

const int MAXN = 1000;

int A,B,ans = 0,shudui[MAXN];

void input_data()
{
    scanf("%d %d",&A,&B);
}

int get_h(int x) //获取x的所有因数之和
{
    int tt = 0;
    for (int i = 1;i <= x-1;i++)
        if ( ( x % i) == 0)
            tt+=i;
    return tt;
}

void get_ans()
{

    for (int i = A;i <= B;i++) //从A到B枚举
        {
            int temp = get_h(i); //获取i的所有因数之和
            if ( temp !=i )
                {
                    int temp2 = get_h(temp); //再获取和的因数之和 嵌套。
                    if (temp2 == i) //如果两个因数之和等于对方 那么久尝试增加答案。
                        {
                            bool flag = true;
                            for (int j = 1;j <= ans;j++) //尝试之前先找找看有没有重复。
                                if (shudui[j] == temp || shudui[j] == temp2)
                                    {
                                        flag = false;
                                        break;
                                    }
                            if (flag)  //没有重复则增加答案。同时记录方案。
                                shudui[++ans] = temp;
                        }
                }
        }
}

void output_ans()
{
    printf("%d
",ans);
}

int main()
{
    input_data();
    get_ans();
    output_ans();
    return 0;
}