本文主要是介绍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.
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;
}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）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
