检查给定的两个数字是否是友好数对

友好数对的定义

友好数对指的是两个正整数中，它们的因数和等于对方的另一个数。

更加详细的说，如果正整数A和B满足以下条件，则我们称它们为友好数对：

A ≠ B

A的所有真因数之和 = B

B的所有真因数之和 = A

例如，(220, 284)就是一组友好数对，因为它们的因数之和分别为：

220的因数之和：1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284

284的因数之和：1 + 2 + 4 + 71 + 142 = 220

判断两个数是否为友好数对

暴力枚举法

最简单的方法是枚举A和B的所有真因数之和，判断它们是否相等。如果相等，则A和B是一组友好数对。

bool isFriendNumber(int A, int B) {
  int sumA = 0, sumB = 0;
  for (int i = 1; i < A; i++) {
    if (A % i == 0) {
      sumA += i;
    }
  }
  for (int i = 1; i < B; i++) {
    if (B % i == 0) {
      sumB += i;
    }
  }
  return sumA == B && sumB == A;
}

这种方法的时间复杂度是O(A+B)，如果A和B很大，则会非常耗时。

优化方法

我们可以通过优化的方式，使得判断友好数对的时间复杂度降为O(sqrt(A+B))，具体方法如下：

先求出每个数的真因数之和，并存储在一个数组中。

然后，对于每对A和B，直接判断它们对应数组中的值是否相等即可。

const int MAXN = 1e6 + 5;
int sum[MAXN];
void init() {
  memset(sum, 0, sizeof(sum));
  for (int i = 1; i < MAXN; i++) {
    for (int j = i*2; j < MAXN; j += i) {
      sum[j] += i;
    }
  }
}
bool isFriendNumber(int A, int B) {
  return sum[A] == B && sum[B] == A;
}

在上面的代码中，我们首先通过一个循环计算出每个数的真因数之和，并将其存储在数组sum中。在判断两个数是否为友好数对时，我们只需要查找它们在数组sum中的对应值是否相等即可。

测试程序

下面是一个测试程序，可以输入两个数字，然后判断它们是否为友好数对：

int main() {
  init();
  int A, B;
  cin >> A >> B;
  if (isFriendNumber(A, B)) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  return 0;
}