0

我有一个 Kattis 问题的解决方案https://open.kattis.com/problems/almostperfect。解决方案被接受，但运行时间太长（>1.00s）。我尝试了一切来解决这个问题。我可以做些什么来进一步提高我的代码的性能？

import java.io.FileInputStream;
import java.util.Scanner;

import java.io.*;
import java.util.*;

public class almostperfect {

public static int perfect(int number){
    // 2 = perfect
    // 1 = almost perfect
    // 0 = not perfect
    int sum = 0;
    int b = 0;
    for(int i=1;i<number;i++)
    {
        if(number%i==0)
        {
            sum = sum + i;
        }
    }
    if(sum == number){
        b = 2;
    } else if(Math.abs(sum-number)<=2){
        b = 1;
    }

    return b;

}


public static void main(String[] args) 
{
    Scanner scan = new Scanner(System.in);
    ArrayList<Integer> input = new ArrayList<Integer>();
    int a;
    int status;
    while(scan.hasNextLong()){
        input.add((int) scan.nextLong());
    }
    for(int i=0; i<input.size(); i++){
    a = input.get(i);
    status = perfect(a);
    if(status==2){
        System.out.println(a+" perfect");
    } else if (status==1){
        System.out.println(a+" almost perfect");
    } else {
        System.out.println(a+" not perfect");
        }
    }

}}
4

2 回答 2

2

计算 的除数时number，不必从 1 循环到number，而是循环到 的平方根number。以 100 为例——如果 2 是 100 的除数，那么 100/2 也是如此。 

int sum = 1;   //1 is always a divisor
int b = 0;
int sqr = (int)Math.sqrt(number);
for(int i=2;i< sqr;i++)
{
    if(number%i==0)
    {
        sum = sum + i;
        sum = sum + number/i;
    }
}
//Check what happens for sqr - if it's a divisor, add it only once
if (sqr * sqr == number)
    sum += sqr;
于 2016-11-01T17:35:35.230 回答
1

你的代码很好，不好的是找到它实现的数字的因素的方法。如果它是一个因素，你需要比蛮力检查每个可能小于数字的数字更聪明。

首先，显然 1始终是一个因数，因为任何数除以 1 都没有余数。此外，根据定义，数字本身不是一个因素。这将要找到的因子限制在 (2 ... n-1) 范围内。

其次，如果你找到一个除数，那么被除数也是一个除数：

dividend = number / divisor -> implies: dividend is also a divisor

这意味着除数总是成对出现（除数也是除数，成对）。必须考虑的一个例外是被除数可能与被除数相同（例如，数字 = 9，除数 = 3 -> 被除数 = 3）。这可以被利用，导致：

第三，当从可能的最小除数 (2) 开始测试时，您发现的第一个除数是可能的最大除数，当您增加测试除数时，除数会稳步下降。这意味着无需显式检查发现为被除数的除数。这意味着测试上限将是除数和被除数相等的地方，即数字的根。

如链接中的问题所述，数字可能在 1 ... 1E9 范围内。1E9的暴力破解方法需要10亿次测试，而利用以上属性的智能版本只需要31621。这大约快30000倍！

于 2016-11-01T18:42:58.093 回答