又遇到了个算完全数的问题,即一个数除了本身以外的公因数,加起来等于本身,如 6 = 1+2+3
,因此 6 是一个完全数。一般这种题目都是要算很多个数,然后每个数都特别大,我一开始的思维就是暴力解法,循环算每个数,然后每个数用取模来找公因数,这样做就超时了。题目最大有 100 个数,每个数最大有 10^8
,这样相当于循环就要 10^10
次了。所以可以缩小内层循环的范围,从 1 开始到数的开方结束。因为约数是一对的,一个小的对应一个大的,如 6 里面 的 2 和 3,所以只要从 1 到开方就可以找到所有小的约数。小的约数的最大可能值就是开方值,像 9、16 这种数的平方。因此这样就可以大大缩小循环次数。然后还有一个坑,就是如果你把 1 算进去,后面还会计算出对应的公因数,即数的本身,但是题目不允许将数本身加进去,所以要把 1 单独拿出来,这样就好了。看了别人的题解
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int main()
{
int n;
cin >> n;
while(n--)
{
int m;
int sum = 0;
cin >> m;
// 暴力解法,如果是 m 是 10^8,就要这么多次乘上 n 的个数,这时极限时间
// for(int i=1; i<m; i++)
// {
// if(m%i == 0)
// sum += i;
// }
if(m==1)
cout << 1 << " is not perfect"<< endl;
else
{
sum = 1;
// 一开始是从 1 到开方,每个合适的都加起来
// 看了别人的题解发现不太对,因为大于开方的后面的只是不计算了
// 但是他们有些的值也是公约数,就像 6 有个公约数 3,但是只算到开方的话
// 只有根号 6,还不到 3呢。所以就是找到小于开方的数,并且找到其对应的公因数。
// 然后还要忽略掉 1,因为如果有 1,对应的公因数就是自己本身,所以得单独加一
for( int i=2; i<=sqrt(m); i++)
{
// if(m%i == 0)
// sum += i;
if(m%i == 0)
{
int y = m/i;
if(y == i) sum += i;
else sum = sum + y+i;
}
}
if( sum == m)
cout << m << " is perfect" << endl;
else
cout << m << " is not perfect" << endl;
}
}
return 0;
}