首页 › 题库 › C/C++编程考级 › C/C++编程二级 › 简答题
简答题 偏难
#13182

亲和数 题目描述 古希腊数学家毕达哥拉斯发现,某些正整数的真因子之和等于另一个数,而另一个数的真因子之和恰好就等于前者。 例如,220 的所有真因子之和为: 1…

亲和数

题目描述

古希腊数学家毕达哥拉斯发现,某些正整数的真因子之和等于另一个数,而另一个数的真因子之和恰好就等于前者。

例如,220 的所有真因子之和为:

1+2+4+5+10+11+20+22+44+55+110=284

而 284 的所有真因子为:

1+2+4+71+142=220

人们对这样的数感到很惊奇,并称之为亲和数。一般地讲,如果两个数中任何一个数都是另一个数的真约数之和,则这两个数就是亲和数。

输入格式

输入数据第一行包含一个数 M,接下有 M 行,每行一个实例,包含两个整数 A,B。

输出格式

对于每个测试实例,如果 A 和 B 是亲和数的话输出 YES,否则输出 NO。

输入样例

2
220 284
100 200

输出样例

YES
NO

说明提示

0≤M≤30

0≤A,B≤100000

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//C代码 #include &lt;stdio.h&gt; // 函数:计算一个数的真因子之和 int sumOfProperDivisors(int num) {    if (num &lt;= 1) {        return 0;    }    int sum = 1; // 1是所有大于1的数的真因子    for (int i = 2; i * i &lt;= num; i++) {        if (num % i == 0) {            sum += i;            if (i != num / i) { // 避免重复添加平方数的情况                sum += num / i;            }        }    }    return sum; } // 函数:判断两个数是否为亲和数 int areAmicableNumbers(int a, int b) {    return (sumOfProperDivisors(a) == b) &amp;&amp; (sumOfProperDivisors(b) == a); } int main() {    int M;    scanf("%d", &amp;M); // 读取测试实例的数量    for (int i = 0; i &lt; M; i++) {        int A, B;        scanf("%d %d", &amp;A, &amp;B); // 读取每对数字        if (areAmicableNumbers(A, B)) {            printf("YES\n");        } else {            printf("NO\n");        }    }    return 0; }</pre><pre class="brush:cpp;toolbar:false">//C++代码 #include &lt;iostream&gt; #include &lt;cmath&gt; // 计算一个数的真因子之和(不包括自身) int getSumOfProperDivisors(int n) {     if (n &lt;= 1) return 0;  // 0和1没有真因子          int sum = 1;  // 1是所有大于1的数的真因子     // 从2遍历到平方根,找出所有因子对     for (int i = 2; i &lt;= std::sqrt(n); i++) {         if (n % i == 0) {             sum += i;             if (i != n / i) {  // 避免平方根重复计算                 sum += n / i;             }         }     }     return sum; } int main() {     int M;     std::cin &gt;&gt; M;  // 读取测试用例数量          while (M--) {         int A, B;         std::cin &gt;&gt; A &gt;&gt; B;  // 读取一对数                  // 计算两数的真因子和         int sumA = getSumOfProperDivisors(A);         int sumB = getSumOfProperDivisors(B);                  // 检查是否为亲和数         if (sumA == B &amp;&amp; sumB == A) {             std::cout &lt;&lt; "YES" &lt;&lt; std::endl;         } else {             std::cout &lt;&lt; "NO" &lt;&lt; std::endl;         }     }          return 0; }</pre>
这道题暂未补解析。