牛客IOI周赛20-普及组 A-完全数

思路：模拟

根据题意，我们需要求出给定 $n$ 的所有除自己以外的约数并求和，最后判断元素和 $sum$ 是否等于给定元素 $n$ ，由于给定 $n$ 的范围最大到 $1e14$ ，所以找约数时找到 $sqrt(n)$ 即可。特别地，为了保证 $n$ 为完全平方数时不重复计算平方根，在加和时需要特判。

代码：

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

int main() {
    ll n;
    cin >> n;
    ll sum = 0;
    for(int i = 2; i <= n / i; i++) {
        if(n % i == 0) {
            if(i * i == n) {
                sum -= i;
            }
            sum += i;
            sum += n / i;
        }
    }
    if(sum + 1 == n) {
        cout << "Pure";
    } else if(sum + 1 > n) {
        cout << "Late";
    } else {
        cout << "Early";
    }
}

复杂度分析

时间复杂度： $O(n ^ {1/2})$
空间复杂度： $O(1)$