首页 > 代码库 > 一道推理题
一道推理题
题目:http://115.28.76.232/problem?pid=1115
题意:初始给定两个完美数1和3,如果都是完美数,那么也是完美数。现在给定一个数,判断
它是否是完美数。
分析:嗯,这道题Mayuyu有两种方法,第一种方法是按照题意有,那么我们进行递归直接判
断。这样做的时间复杂度很高,通过打表对一些数的观察发现,只需要看这个数是否只由3和5组成。
打表代码:
#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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。