Java：2D阵列的总和，其中M [i] [j] =（int）i / j

T - number of test cases | 1<=T<=10 and n - number of elements | 1<=n<=1000000

T - 测试用例数| 1 <= T <= 10且n - 元素数| 1 <= N <= 1000000

if (T >= 1 && T <= 10) {
    for (int i = 0; i < T; i++) {
                int n = sc.nextInt();
                if (n > 0 && n <= 1000000) {
                    array = new int[n][n];
                    System.out.print("\n" + sumOfArray(array, n));
                }
             }
          }

Need to find the sum of M[i][j], where M[i][j] = (int) i/j;

需要找到M [i] [j]的和,其中M [i] [j] =(int)i / j;

I have written the code, but for n>10000, I start getting OOM, (for obvious reason).

我已经编写了代码,但是对于n> 10000,我开始得到OOM,(显而易见的原因)。

If someone can help me with it, it'll be great. Need a whole new approach on solving the problem.

如果有人可以帮助我,它会很棒。需要一种全新的方法来解决问题。

Eg.

Input   Output
2       
2       4
4       17

1 个解决方案

#1

Here It is obvious that you don't need to store the values in the matrices because It is not possible to have that much space (Array[10000][10000]) available to allocate. So you need to think somehow in a mathematical way.

这里显然您不需要将值存储在矩阵中,因为不可能有足够的空间(Array [10000] [10000])可用于分配。所以你需要以某种数学方式思考。

Consider a 4x4 Matrix and represent each element in the term of i,j.

考虑一个4x4矩阵并表示i,j项中的每个元素。

1,1 1,2 1,3 1,4
2,1 2,2 2,3 2,4
3,1 3,2 3,3 3,4
4,1 4,2 4,3 4,4

Now we can represent here that what is stored in each of these elements.

现在我们可以在这里表示存储在每个元素中的内容。

1/1 1/2 1/3 1/4   (In Integers)     1 0 0 0
2/1 2/2 2/3 2/4   ============>     2 1 0 0
3/1 3/2 3/3 3/4                     3 1 1 0
4/1 4/2 4/3 4/4                     4 2 1 1

Tackle this matrix by dividing it into columns and solve each of the columns. For the first column series would be 1+2+3+4.Then for the column number two(2) the series would be 0+1+1+2.

通过将此矩阵分成列并解决每个列来解决此矩阵。对于第一列系列将是1 + 2 + 3 + 4.然后对于列号二(2),该系列将是0 + 1 + 1 + 2。

Notice here that for ith column first i-1 values are zeros and then i values are same in the column. Then value is increased. Again it will be same for i values. Again increases by 1 and so on.

请注意,对于第i列,第一个i-1值为零,然后i值在列中相同。然后价值增加。对于i值,它也是相同的。再增加1,依此类推。

So in ith column value get increased on the jth element where j%i==0.

因此,在第i个列中,值增加了第j个元素,其中j%i == 0。

So you can implement this logic in 1-D array and Complexity of this approach will be O(n logn) for each testcase.

因此,您可以在一维数组中实现此逻辑,并且对于每个测试用例,此方法的复杂性将为O(n logn)。

Code:

import java.util.Scanner;

public class Main
{
    public static void main(String args[])
    {
        Scanner sc=new Scanner(System.in);

        int testcases=sc.nextInt();

        while(testcases-- >0)
        {
            int n=sc.nextInt();

            long array[]=new long[n+1]; //Take long array to avoid overflow

            for(int i=1;i<=n;i++)
            {
                for(int j=i;j<=n;j+=i)
                {
                    array[j]++;          //This will store that which elements get increased
                                         //from zero how many times
                }
            }

            //Now we can do summation of all elements of array but we need to do prefix sum here

            long sum=0;
            for(int i=1;i<=n;i++)
            {  
                array[i]+=array[i-1];
                sum+=array[i];
            }

            System.out.println(sum);
        }
    }
}

#1