c - 我怎样才能降低这段代码的复杂性(如下所示)？

Question

关闭。此题需要 details or clarity 。目前不接受答案。

---

想要改进这个问题吗？通过 editing this post 添加详细信息并澄清问题.

已关闭 6 年前。

Improve this question

问题陈述: 求 N 以下所有 3 或 5 的倍数之和。

输入格式:第一行包含 T 表示测试用例的数量。接下来是 T 行，每行包含一个整数 N。

约束:

1 <= T <= 10^5

1 <= N <= 10^9

输出格式:对于每个测试用例，打印一个整数，表示 N 以下的 3 或 5 的所有倍数之和。

这是我的代码:

#include <stdio.h>

int main() {
    long t,i,x;
    scanf("%ld",&t);
    long y[t];
    for(i=0; i<t; i++) {
        scanf("%ld",&x);
        long j,k,sum= 0;
        if(x<=3)
            sum= 0;
        else if(x<=5)
            sum= 3;
        else {
            for(j=3; j<x; j+=3)
                sum= sum + j;
            for(j=5; j<x; j+=5)
                if(j%3!=0)
                  sum = sum + j;
        }   
        y[i] = sum;
    }   
    for(i=0; i<t; i++) {
        printf("%ld\n",y[i]);
    }
    return 0;
}    

Answer 1

存在一个时间复杂度为 O(T) 的解:

使用整数和的公式1+2+3+...+n = n*(n+1)/2。

另请注意 3+6+9+...+(3*n) = 3*(1+2+3+...+n) = 3*n*(n+1)/2.

算出有多少个数字可以被 3 整除。计算它们的总和。

算出有多少个数字可以被 5 整除。计算它们的总和。

算出有多少个数字可以被 15 (=3*5) 整除。计算它们的总和。

总和为sum3 + sum5 - sum15。可被 3 和 5(因此被 15)整除的数字都在 sum3 和 sum5 中，因此除非我们减去 sum15，否则它们将被计算两次。

请注意，总和会溢出 32 位整数，因此请确保使用 64 位整数类型。