题解 | 亲和数

#include<bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    int maxr = 0; //记录最大的数，规定保存真因子之和的数组
    vector< pair<int, int> > arr; //保存区间
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        arr.push_back({l, r});
        if (r >= maxr)
            maxr = r;
    }
    vector<int> sum(maxr + 1, 0); //保存真因子之和，相当于空间换时间判断x是否为亲和数（有点巧妙）
    for (int i = 1; i <= maxr; i++) {
        for (int j = i * 2; j <= maxr; j += i) { 
            	sum[j] += i;
        }
    }

    for (int i = 0; i < arr.size(); i++) {
    	if (arr[i].first>arr[i].second){ //这个算是测试样例的坑，测试点有l>r的情况，要输出No，搞了半天才发现，题目压根没说！
    		cout << "No" << endl;
    		continue;
		}
        bool flag = true;
        for (int j = arr[i].first; j <= arr[i].second; j++) {
            if (sum[j] <= maxr && j!=sum[j] && sum[sum[j]] == j) { //判断x是否为亲和数，注意x和y不能相等（x=j,y=sum[j]），算是题目的坑了
                cout << j << endl;
                flag = false;
                break;
            }
        }
        if (flag)
            cout << "No" << endl;
    }


}