首页 > 代码库 > 一道推理题

一道推理题

题目:http://115.28.76.232/problem?pid=1115

 

题意:初始给定两个完美数13,如果都是完美数,那么也是完美数。现在给定一个数,判断

     它是否是完美数。

 

分析:嗯,这道题Mayuyu有两种方法,第一种方法是按照题意有,那么我们进行递归直接判

     断。这样做的时间复杂度很高,通过打表对一些数的观察发现,只需要看这个数是否只由35组成。

   

打表代码:

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <math.h>

using namespace std;
typedef long long LL;

bool dfs(int n)
{
    if(n == 1 || n == 3)
        return true;
    if(n < 0) return false;
    int t = n + 2;
    int x = (int)sqrt(1.0*n + 2);
    for(int i=3; i<=x; i++)
    {
        if(t % i == 0)
        {
            int a = i;
            int b = t / a;
            return dfs(a - 2) && dfs(b - 2);
        }
    }
}

int main()
{
    int n;
    for(n=1;n<=10000;n++)
        if(dfs(n))
            cout<<n + 2<<endl;
    return 0;
}

 

当然还有一种方法就是直接推理做,已经知道,如果有

 

     

 

带入上式得到,如果一直推下去得到很多个这样的数相乘,而最终都会转化为

若干个3和若干个5相乘的形式。

 

代码:

#include <iostream>
#include <string.h>
#include <stdio.h>

using namespace std;

int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        n += 2;
        while(n % 3 == 0) n /= 3;
        while(n % 5 == 0) n /= 5;
        if(n == 1) puts("Yes");
        else puts("No");
    }
    return 0;
}