题目描述

若一个数除了自己本身以外，所有因子之和等于它自己，那么称这个数为“完全数”。
例如，6的因子有1,2,3,6，1+2+3=6，所以6是完全数。
而8的因子有1,2,4,8，1+2+4=7，所以8不是完全数。
同样的，我们定义：若一个数除了自己本身以外，所有因子之和大于它自己，那么称这个数为“过剩数”，例如12。
若一个数除了自己本身以外，所有因子之和小于它自己，那么称这个数为“不足数”，例如8。
输入一个数，判断它是完全数、过剩数还是不足数。

输入描述

一个正整数

输出描述

如果是完全数，则输出“Pure”。
如果是过剩数，则输出“Late”。
如果是不足数，则输出“Early”。

示例1

输入

28

输出

Pure

说明

1+2+4+7+14=28

示例2

输入

15

输出

Early

说明

1+3+5=9<15

示例3

输入

72

输出

Late

说明

1+2+3+4+6+8+9+12+18+24+36>72

备注

对于20%的数据，数据范围1 。
对于50%的数据，数据范围2 。
对于100%的数据，数据范围3 。

解法

思考

数据范围1e14，如果要一个数一个数的试是否能够被n整除肯定要超时。
由于一个数n的因数a如果大于根号n，那么必定存在因数b<n使得ab=n。（否则如果a、b都大于根号n，则ab大于n）。
因此数据范围缩小到1~√n。1e7不至于超时。

i从2到根号n循环，如果n能整除i，因数和就加上i和n/i；当i正好等于根号n时需要特判。

AC代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long n;
    scanf("%lld",&n);
    long long sum=1;
    long long k=sqrt(n);
    for(long long i=2;i<k;i++)
    {
        if(n%i==0)//n能够整除i
        {
            sum+=i+n/i;
        }
    }
    if(n%k==0)
    {
        sum+=k;
        if(n/k!=k)sum+=n/k;
    }
    if(sum>n)puts("Late");
    else if(sum<n)puts("Early");
    else puts("Pure");
    return 0;
}