题解 | 完数VS盈数

显然，我们只要求出给定数的所有因数之和，就可以判断这个数是否为完数或盈数。和正常找因数的过程一样，我们只要在之前寻找能够整除给定数的整数即可；对应只需要将之前的因数和加上这个新的因数数和与之相对的之后的因数。特别地，若给定数是完全平方数，则需要且仅需要加一次；由于求和时不包括数本身但是包括，所以最终或者最初的和变量应当加。

显然一个数不可能既是完数又是盈数。因此，我们可以使用else来轻微地降低成本。

#include <bits/stdc++.h>
#define _CRT_SECURE_NO_DEPRECATE

int byFactorAdder(int n) {
    int sum = 1;
    for (int i = 2; i <= (int)std::sqrt(n); i++) {
        if (n % i) continue;
        else {
            sum += i + n / i;
        }
    }
    return n / std::sqrt(n) == (int)std::sqrt(n) ? sum - (int)std::sqrt(
               n) : sum;
}

bool isPerfect(int n) {
    return byFactorAdder(n) == n;
}

bool isSurplus(int n) {
    return byFactorAdder(n) > n;
}

int main() {
    std::vector<int> e, g;
    for (int i = 2; i <= 60; i++) {
        if (isPerfect(i)) e.push_back(i);
        else if (isSurplus(i)) g.push_back(i);
    }
    std::cout << "E: ";
    for (int i : e) {
        std::cout << i << " ";
    }
    std::cout << std::endl << "G: ";
    for (int i : g) {
        std::cout << i << " " << std::endl;
    }
    return 0;
}

当然这题因为给出的样本空间极小且固定，直接输出答案也并非不可；时间复杂度也仅有。

#include <bits/stdc++.h>
#define _CRT_SECURE_NO_DEPRECATE

int main() {
    std::cout << "E: 6 28" << std::endl << "G: 12 18 20 24 30 36 40 42 48 54 56 60" << std::endl;
    return 0;
}