整数除法矩阵之和

Question

以下是HackerEarth挑战赛中的一个问题 -

Roy有一个大小为NxN的矩阵.行和列的编号从1到N.第i行的第j列包含整数除法i/j.

换句话说,Matrix [i] [j] = int(i/j)其中1≤i,j≤N.

Your task is to find sum of this matrix i.e.

sum = 0
for i=1 to N-1
    for j=1 to N-1
        sum += Matrix[i][j]
Constraints:
1 ? T ? 10
1 ? N ? 1000000

这是我解决这个问题的方法

#include <cstdio>
#include <cassert>
using namespace std;
#define MAXT 10
#define MAXN 1000000
long long solve(long long N){
    long long ans = 0;
    for(int i=1;i<N-1;i++)
    {
    for(int j=1; j<N-1 ; j++)
    {
        int temp = N*i/j;
        ans = ans + temp;
    }
    }
    return ans;
}
int main(){
    int T, N;
    scanf("%d", &T);
    assert(T>0 and T<=MAXT);
    while(T--){
        scanf("%d", &N);
        assert(N>0 and N<=MAXN);
        printf("%lld\n", solve((long long)N));
    }
    return 0;
}

但是这个程序的输出并不正确.

所以请告诉我,如果我在这里做得对.如果是,我还可以做些什么来优化此代码.谢谢你的帮助.

Answer 1

请注意,int(i/j)对于较大的值,变化不大j

也就是说,如果j = 1000 int(i/j)将0用于1-1000,那么这将是1对1000-2000,等等.使用此事实,您可以创建复杂度更低的算法.

例如,如果N = 50000,那么j = 1000,你将获得0... (1000)时间+ 1 ..(1000)次+ 2..(1000)次......最49,000/1000... (1000)多次.

即 div = N/j ans += (div *(div-1) *j)

如果N/j不是整数,您还需要进行更正,如下面的代码所示.

long long solve(long long N){
    long long ans = 0;
    long long div, mod;
    for (int i = 1; i <= N; i++)
    {
        div = N/i;
        mod = i- N%i;
        ans += (div * (div+1) * i)/2;

        // For the case when N does not go directly into i,
        // e.g. N = 47500, i = 1000, the last 500 need to be removed from the sum
        ans -= (mod-1) * div;
        printf ("\n i = %d, ans = %lld",i,ans);
    }
    return ans;
}

这是O(n)复杂性.

编辑:已更正以修复预期结果.