hdu 1528 Perfection(数论·因子和·C++·java)

2024-03-27 23:18

本文主要是介绍hdu 1528 Perfection(数论·因子和·C++·java),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目:http://poj.org/problem?id=1528

Perfection
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 11909 Accepted: 5595

Description

From the article Number Theory in the 1994 Microsoft Encarta: ``If a, b, c are integers such that a = bc, a is called a multiple of b or of c, and b or c is called a divisor or factor of a. If c is not 1/-1, b is called a proper divisor of a. Even integers, which include 0, are multiples of 2, for example, -4, 0, 2, 10; an odd integer is an integer that is not even, for example, -5, 1, 3, 9. A perfect number is a positive integer that is equal to the sum of all its positive, proper divisors; for example, 6, which equals 1 + 2 + 3, and 28, which equals 1 + 2 + 4 + 7 + 14, are perfect numbers. A positive number that is not perfect is imperfect and is deficient or abundant according to whether the sum of its positive, proper divisors is smaller or larger than the number itself. Thus, 9, with proper divisors 1, 3, is deficient; 12, with proper divisors 1, 2, 3, 4, 6, is abundant."
Given a number, determine if it is perfect, abundant, or deficient.

Input

A list of N positive integers (none greater than 60,000), with 1 <= N < 100. A 0 will mark the end of the list.

Output

The first line of output should read PERFECTION OUTPUT. The next N lines of output should list for each input integer whether it is perfect, deficient, or abundant, as shown in the example below. Format counts: the echoed integers should be right justified within the first 5 spaces of the output line, followed by two blank spaces, followed by the description of the integer. The final line of output should read END OF OUTPUT.

Sample Input

15 28 6 56 60000 22 496 0

Sample Output

PERFECTION OUTPUT15  DEFICIENT28  PERFECT6  PERFECT56  ABUNDANT
60000  ABUNDANT22  DEFICIENT496  PERFECT
END OF OUTPUT
分析:
由于a!=-1 && a!=1所以b是除number本身外的所有因子。完美数就是所有因子的和对number进行素因子分解,分解情况:a1-q1 a2-q2 …… an-qn 那么所有的因子和应该等于:(1+a1+a1^2+……+a1^q1)(1+a2+a2^2+……+a2^q2)……(1+an+an^2+……+an^qn)  对于每一项:1+a+a^2+……+a^n等比数列求和,当:
n是奇数时,乘积等于(1+a^(n/2+1))(1+a+……+a^(n/2)). (奇转偶)
n是偶数时,乘积等于(1+a^(n/2+1))(1+a+……+a^(n/2-1))+a^(n/2).   (偶转奇)
用C++很快写完并成功1A,想到刚学java,于是试着用java仿照着写写看,好家伙,运行时间,内存消耗都增长了不少,而且还莫名的错了好几次。CE因为类名的问题,WA是因为没有及时在输入0时跳出,PE则是System.out.println("PERFECTION OUTPUT\n");   ||-_-

c++:
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int fac[300],p[300],top;
void resolve(int x){top=0;memset(p,0,sizeof(p));for(int i=2;i*i<=x;i++){if(x%i==0){fac[top]=i;while(x%i==0){x/=i;p[top]++;}top++;}}if(x>1){fac[top]=x;p[top++]++;}
}
int power(int a,int n){int ans=1,temp=a;while(n){if(n&1) ans=ans*temp;temp=temp*temp;n>>=1;}return ans;
}
int cal(int a,int n){if(n==2) return (1+a+a*a);if(n==1) return (1+a);if(n&1) return (1+power(a,n/2+1))*cal(a,n/2);else return (1+power(a,(n/2+1)))*cal(a,(n/2-1))+power(a,(n/2));
}
int main()
{//freopen("cin.txt","r",stdin);int a;printf("PERFECTION OUTPUT\n");while(cin>>a&&a){resolve(a);int res=1;for(int i=0;i<top;i++){res=res*cal(fac[i],p[i]);}printf("%5d  ",a);res=res-a;if(res<a) puts("DEFICIENT");else if(res==a) puts("PERFECT");else puts("ABUNDANT");}printf("END OF OUTPUT\n");return 0;
}
java:
import java.util.*;
import java.lang.String;
public class Main {static int[] fac=new int [300],p=new int [300];static int top;static void resolve(int x){top=0;Arrays.fill(p,0); //Arrays belong to utilfor(int i=2;i*i<=x;i++){if(x%i==0){fac[top]=i;while(x%i==0){x/=i;p[top]++;}top++;}}if(x>1){fac[top]=x;p[top++]++;}}static int power(int a,int n){int ans=1,temp=a;while(n>0){if(n%2==1) ans=ans*temp;temp=temp*temp;n>>=1;}return ans;}static int cal(int a,int n){if(n==2) return (1+a+a*a);if(n==1) return (1+a);if(n%2==1) return (1+power(a,n/2+1))*cal(a,n/2);else return (1+power(a,(n/2+1)))*cal(a,(n/2-1))+power(a,(n/2));}public static void main(String[] args) {int a;Scanner sc=new Scanner(System.in);System.out.println("PERFECTION OUTPUT");while(sc.hasNextInt()){a=sc.nextInt();if(a==0) break;resolve(a);int res=1;for(int i=0;i<top;i++){res=res*cal(fac[i],p[i]);}String str;res=res-a;if(res<a) str="DEFICIENT";else if(res==a) str="PERFECT";else str="ABUNDANT";System.out.printf("%5d  %s\n",a,str);}System.out.printf("END OF OUTPUT\n");}}
/*class perfect is public, should be declared in a file named perfect.java
public class perfect {^
把perfect 改成Main即可。(public修饰的类名必须和文件名一样)
*/



这篇关于hdu 1528 Perfection(数论·因子和·C++·java)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/853721

相关文章

Java通过驱动包(jar包)连接MySQL数据库的步骤总结及验证方式

《Java通过驱动包(jar包)连接MySQL数据库的步骤总结及验证方式》本文详细介绍如何使用Java通过JDBC连接MySQL数据库,包括下载驱动、配置Eclipse环境、检测数据库连接等关键步骤,... 目录一、下载驱动包二、放jar包三、检测数据库连接JavaJava 如何使用 JDBC 连接 mys

C++中NULL与nullptr的区别小结

《C++中NULL与nullptr的区别小结》本文介绍了C++编程中NULL与nullptr的区别,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编... 目录C++98空值——NULLC++11空值——nullptr区别对比示例 C++98空值——NUL

SpringBoot线程池配置使用示例详解

《SpringBoot线程池配置使用示例详解》SpringBoot集成@Async注解,支持线程池参数配置(核心数、队列容量、拒绝策略等)及生命周期管理,结合监控与任务装饰器,提升异步处理效率与系统... 目录一、核心特性二、添加依赖三、参数详解四、配置线程池五、应用实践代码说明拒绝策略(Rejected

C++ Log4cpp跨平台日志库的使用小结

《C++Log4cpp跨平台日志库的使用小结》Log4cpp是c++类库,本文详细介绍了C++日志库log4cpp的使用方法,及设置日志输出格式和优先级,具有一定的参考价值,感兴趣的可以了解一下... 目录一、介绍1. log4cpp的日志方式2.设置日志输出的格式3. 设置日志的输出优先级二、Window

一文详解SpringBoot中控制器的动态注册与卸载

《一文详解SpringBoot中控制器的动态注册与卸载》在项目开发中,通过动态注册和卸载控制器功能,可以根据业务场景和项目需要实现功能的动态增加、删除,提高系统的灵活性和可扩展性,下面我们就来看看Sp... 目录项目结构1. 创建 Spring Boot 启动类2. 创建一个测试控制器3. 创建动态控制器注

Java操作Word文档的全面指南

《Java操作Word文档的全面指南》在Java开发中,操作Word文档是常见的业务需求,广泛应用于合同生成、报表输出、通知发布、法律文书生成、病历模板填写等场景,本文将全面介绍Java操作Word文... 目录简介段落页头与页脚页码表格图片批注文本框目录图表简介Word编程最重要的类是org.apach

Spring Boot中WebSocket常用使用方法详解

《SpringBoot中WebSocket常用使用方法详解》本文从WebSocket的基础概念出发,详细介绍了SpringBoot集成WebSocket的步骤,并重点讲解了常用的使用方法,包括简单消... 目录一、WebSocket基础概念1.1 什么是WebSocket1.2 WebSocket与HTTP

SpringBoot+Docker+Graylog 如何让错误自动报警

《SpringBoot+Docker+Graylog如何让错误自动报警》SpringBoot默认使用SLF4J与Logback,支持多日志级别和配置方式,可输出到控制台、文件及远程服务器,集成ELK... 目录01 Spring Boot 默认日志框架解析02 Spring Boot 日志级别详解03 Sp

java中反射Reflection的4个作用详解

《java中反射Reflection的4个作用详解》反射Reflection是Java等编程语言中的一个重要特性,它允许程序在运行时进行自我检查和对内部成员(如字段、方法、类等)的操作,本文将详细介绍... 目录作用1、在运行时判断任意一个对象所属的类作用2、在运行时构造任意一个类的对象作用3、在运行时判断

java如何解压zip压缩包

《java如何解压zip压缩包》:本文主要介绍java如何解压zip压缩包问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java解压zip压缩包实例代码结果如下总结java解压zip压缩包坐在旁边的小伙伴问我怎么用 java 将服务器上的压缩文件解压出来,