Time Limit: 3 second
Memory Limit: 2 MB
问题描述
所谓完全数,就是这个数除了它本身的约数之和也等于这个数,比如说6的约数有1、2、3,而1+2+3=6,所以6是个完全数。
编程输入一个整数n,如果n是完全数输出Yes,否则输出No。
Sample Input
6
Sample Output
Yes
Sample Input
100
Sample Output
No
【题目链接】:http://noi.qz5z.com/viewtask.asp?id=rlz01
【题解】
枚举n的因子(1..sqrt(n))就好;
i*i的只能算一次,1的话n/1不能算,因为不能为本身;
/*
n非常大的话有个数论的结论;
即对于一个梅森素数mp = 2^p - 1,必有 一个完全数 2^(p-1) * mp;
比如:p=3
Mp=2^3-1=7也是素数
则有完全数2^(3-1)*(2^3-1)=4*7=28
所以枚举p,如果p是质数,就能搞到一个完全数
*/
【完整代码】
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
int n;
int main()
{
cin >> n;
int maxl = sqrt(double(n));
int sum = 0;
for (int i = 1;i <= maxl;i++)
if (n%i==0)
{
sum+=i;
if ((n/i)!=i && i!=1)
sum+=(n/i);
if (sum > n)
{
puts("No");
return 0;
}
}
if (sum < n)
puts("No");
else
puts("Yes");
return 0;
}