java ADACON:Ada和连接SPOJ（TLE）

Question

This是来自SPOJ的一个问题。我快发疯了。需要帮助来提高其时间复杂性。我知道有一个测试用例会失败。但我会在时间复杂度降低后处理它

Ada the Ladybug was on a trip with her friends. They each bought a souvenir there. As all of them are mathematicians, everybody bought a number. They want to modify the numbers to have some connection between each other. They have decided to modify the numbers sou they would have their GCD greater than 1 ( gcd(a₁,a₂,a₃,...,a_N) > 1). Anyway it is not easy to change a number - the only thing they can do is to go to a proffesor in mathematics, which could forge a number A into number A+1 or A-1. As this operation is not cheap, they want to minimize number of such operations. A number might be forged any number of times.

注意：gcd（a，0）==a（因此两个0的gcd也是0）

输入
第一行包含一个整数1 ≤ N ≤ 3*10^5，即在旅途中的朋友人数（以及数字的数量）

第二行包含N个整数0 ≤ a_i ≤ 10^6

输出
打印具有最少操作数的单行，以便在所有数字之间建立连接

示例输入
5
397631
示例输出
2
示例输入2
9
3 4 5 7 8 9 11 12 13
示例输出2
6
示例输入3
5
7 11 17 1
示例输出3
五,

方法

First i find the primes upto (largest/2 + 1) element in the given array of numbers(using function findPrimes()). And then for every element in the array, find how many operations are going to be needed for each of the primes to be its divisor. The smallest summation for each prime, I am printing as solution.

代码

import java.io.*;


public class Main
{
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int largest = Integer.MIN_VALUE;
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        String[] strArr = br.readLine().split(" ");
        for(int i = 0 ; i < n ; i++)
        {
            arr[i] = Integer.parseInt(strArr[i]);
            if(arr[i] > largest)
            {
                largest = arr[i];
            }
        }
        func(n,arr,largest);

    }

    public static void func(int n,int[] arr,int largest)
    {
        int[] primes = findPrimes(largest / 2 + 1);
        //int[] primes = findPrimes((int)Math.sqrt(largest));
        int lenOfPrimes = primes.length;
        int[] mat = new int[lenOfPrimes];
        for(int j = 0 ; j < lenOfPrimes ; j++)
        {
                if(arr[0] < primes[j])
                {
                    mat[j] = primes[j] - arr[0];
                }
                else if(arr[0] % primes[j] == 0)
                {
                    mat[j] = 0;
                }
                else
                {
                    int rem = arr[0] % primes[j];
                    mat[j] = Math.min(rem,primes[j] - rem);
                }

        }
        for(int i = 1 ; i < n ; i++)
        {
            for(int j = 0 ; j < lenOfPrimes ; j++)
            {
                if(arr[i] < primes[j])
                {
                    mat[j] = mat[j] + primes[j] - arr[i];
                }
                else if(arr[i] % primes[j] == 0)
                {
                    mat[j] = mat[j] + 0;
                }
                else
                {
                    int rem = arr[i] % primes[j];
                    mat[j] += Math.min(rem,primes[j] - rem);
                }
            }
        }

        int smallest = Integer.MAX_VALUE;
        for(int i = 0 ; i < lenOfPrimes ;i++)
        {
            if(mat[i] < smallest)
                smallest = mat[i];
        }

        System.out.println(smallest);
    }

    public static int[] findPrimes(int upto)
    {
        boolean[] primes = new boolean[upto + 1];
        for(int i = 0 ; i < upto + 1 ; i++)
            primes[i] = true;

        int count = 0;
        primes[0] = primes[1] = false;

        int limit = (int)Math.sqrt(upto + 1);
        for(int i = 2 ; i < upto + 1; i++)
        {
            if(primes[i] == true)
            {
                count++;
                if(i <= limit)
                {
                    for(int j = i * i ; j < upto + 1 ; j += 2 * i)
                    {
                        primes[j] = false;
                    }
                }
            }
        }

        int[] primeContainer = new int[count];
        int index = 0;
        for(int i = 2 ; i < upto + 1 ; i++)
        {
            if(primes[i] == true)
            {
                primeContainer[index++] = i;
                if(index == count)
                    break;
            }
        }
        return primeContainer;
    }
}

Answer 1

你正在尝试的解决方案会给你正确的答案。但由于在1000000之前有很多素数，（~78000），因此78000*300000肯定会给出TLE
试着用筛子来思考。eratosthenes的筛子在O（nlogn）时间内工作

现在你们已经知道，你们要改变数字，使它可以被一些素数整除。（在你的算法中，你只考虑素数）。现在让我们取一个素数，比如说7。现在您需要找到从0到3的数字转换数，因为您需要将这些数字更改为0。类似地，您需要找到从4到10的数字数量，因为考虑到最小操作，您将把它们更改为7，以使它们可以被7整除。同样地，你也会对从11到17的数字做同样的处理，将它们改为14，依此类推，直到1000000为止。对于所有素数，都需要这样做。这可以通过使用筛子来实现

这种情况下的操作数为n/2+n/3+n/5+n/7+n/11+…~恩洛恩

您可以从这里阅读更多关于sieve的信息：https://www.geeksforgeeks.org/sieve-of-eratosthenes/

Answer 2

也许已经太晚了，但让我来回答这个问题。 我用下面的方法解决了这个问题。 对于所有15个测试用例，我的Java解决方案在SPOJ上需要3.8秒。 1.在O（对数n）中求n的素因子 资料来源https://www.geeksforgeeks.org/prime-factorization-using-sieve-olog-n-multiple-queries/ 2.在计算因式分解时，将素数因子存储在数组中，比如uniqueprimewhichedidsatleastonenumber[] 这里有一个问题，就是在这个uniqueprimewhichedidsatlestoneNumber中始终保留2，如果它不可用的话。 uniqueprimewhichedividsatleastonenNumber[0]=2 现在你可以通过这些素数的最小循环求和

        long minTemp = 0, minAns = Long.MAX_VALUE;
        for (int i = 0; i < UniquePrimeWhicheDividsAtleastOneNumber.length; i++) {
            for (int j = 0; j < n; j++) {
                int rem = InputNumbers[j] % UniquePrimeWhicheDividsAtleastOneNumber[i];
                minTemp += Math.min(rem, UniquePrimeWhicheDividsAtleastOneNumber[i] - rem);
                if (minTemp > minAns)
                    break;// no need to compute sum of reminders if it exceeded the current minimum.
            }
            minAns = Math.min(minAns, minTemp);
            minTemp = 0;
        }
        
        minAns  > is your answer.