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

很明显，你不需要将值存储在矩阵中，因为不可能有那么多的空间(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列firsti-1值为零，然后i values列中的值相同。然后增加value。同样，对于i值也是如此。再次增加1，依此类推。

因此，ith列值在j%i==0的jth元素上获取increased。

因此，您可以在数组中实现此逻辑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);
}
}
}