Java：二维数组的总和，其中 M[i][j] = (int) i/j

Question

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));
                }
             }
          }

需要求M[i][j]的和，其中M[i][j] = (int) i/j;

我已经编写了代码，但是对于 n>10000，我开始出现 OOM，（原因很明显）。

如果有人能帮助我，那就太好了。需要一种全新的方法来解决问题。

例如。

Input   Output
2       
2       4
4       17

Answer 1

这里很明显，您不需要将值存储在矩阵中，因为不可能有那么多 space (Array[10000][10000]) 可用于分配。所以你需要以某种方式思考mathematical。

考虑一个 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

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

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

通过将矩阵分成列来解决这个矩阵，并解决每个 columns。对于第一列系列将是 1+2+3+4。然后对于列号 two(2)，系列将是 0+1+1+2。

请注意，对于 ith 列，first i-1 值为零，然后 i values 在该列中相同。然后增加value。 i 值同样如此。再次增加 1 等等。

所以在 ith 列中的值在 jth 元素上得到 increased，其中 j%i==0.

因此您可以在 1-D 数组中实现此逻辑，并且对于每个测试用例，此方法的复杂度为 O(n logn)。

代码：

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);
        }
    }
}

Java：二维数组的总和，其中 M[i][j] = (int) i/j

Java: Sum of 2D array where the M[i][j] = (int) i/j

java

arrays

2d

sum

matrix