如何降低此代码的复杂性

Question

1<T<10 (where T is number of test cases)
1<N<1000

我们必须优化此代码。

我尝试将所有数字的因子从N到1的N^2。但这仍然给TLE

int count = 0;
for (int i = 1; i <= N; i++)
{
    for (int j = 1; j <= N; j++)
    {
        for (int k = 1; k <= N; k++)
        {
            if ((i * j) % k == 0)
             count++;
        }
    }
}
return count;

所以我猜它应该在O（N ^ 2）中运行

Answer 1

减少运行时间的一种简单方法是使用最大公约数（在此使用c ++ 17），如下所示：

#include <numeric>
int main(){
    int N = 1000;
    int count = 0;
    for (int k = 1; k <= N; ++k){
        for (int j = 1; j <= N; ++j){
            int gcd = std::gcd(j,k);
            count += N/(k/gcd);
        }
    }
    return count;
}

这具有O（N ^ 2 log（N））运行时间。我相信通过k的因子分解可以进一步降低复杂性，但是解决方案可能变得更加复杂。

编辑：在O（1）中可能有一个简单的数学公式来解决这个问题。这需要一些思考。

Answer 2

离线编写代码并运行它。在文件中运行离线写入时。

fprintf(f,"a[%d]=%d;",n,function(n));

其中a是1001个元素的向量。使用生成的代码。

int function(int N) {
int count = 0;
for (int i = 1; i <= N; i++)
{
    for (int j = 1; j <= N; j++)
    {
        for (int k = 1; k <= N; k++)
        {
            if ((i * j) % k == 0)
             count++;
        }
    }
}
return count;
}

int main() {
FILE* f = fopen("data.cpp","w");
for(int i=1;i<=1000;++i) {
fprintf(f,"a[%d]=%d;",n,function(n));
if(i%10==0) fprintf(f,"\n");
}
fclose(f);
return 0;
}

您可以在PC和data.cpp中运行此代码，您将获得可用于实际解决方案的新部分源代码。

int main() {
int a[1001];
// <- generated code here

// here you will need to use a as a cached value instead of computing

return 0;
}