[已解决]求帮忙看一下代码问题出在哪

初莫M

题目是输入描述
输入一个整数数n。0≤n≤1e12
。

输出描述
输出一个整数表示在[0,n]
中，有多少个数可以被3或5整除,如果结果是0，请输出“zero”,否则请输出结果。
我的代码是
#include<stdio.h>
int main()
{
    int n,i=0,sum=0;
    scanf("%d",&n);
    for(;i<=n;i++)
    {
        if(i%3==0||i%5==0)
            sum=sum+1;
    }
    if(sum==0) printf("zero");
    if(sum>0) printf("%d",sum);
}
平台显示时间超限,错在哪了啊

最佳答案

月排行榜 / 总排行榜

isdkz

2023-9-28 22:25:23

您的代码时间复杂度为O(n)，当输入n较大时，程序需要循环极多次，导致超时。可以考虑优化算法，将时间复杂度降为O(1)。

根据题目，我们需要统计在[0,n]中，有多少个数可以被3或5整除。我们可以先分别统计出在[0,n]中，有多少个数可以被3或5整除，再减去在[0,n]中，有多少个数可以被15整除（因为15同时是3和5的倍数，会被重复计算）。具体代码如下：

#include <stdio.h>

int main()
{
    long long n;
    scanf("%lld", &n);

    long long cnt3 = n / 3;  // 可以被3整除的数的个数
    long long cnt5 = n / 5;  // 可以被5整除的数的个数
    long long cnt15 = n / 15;  // 可以被15整除的数的个数

    long long ans = cnt3 + cnt5 - cnt15;  // 最终答案

    if (ans == 0) printf("zero");
    else printf("%lld", ans);

    return 0;
}

注意，由于n的范围较大，需要使用long long类型存储。

跳转到最佳答案楼层

isdkz

您的代码时间复杂度为O(n)，当输入n较大时，程序需要循环极多次，导致超时。可以考虑优化算法，将时间复杂度降为O(1)。

根据题目，我们需要统计在[0,n]中，有多少个数可以被3或5整除。我们可以先分别统计出在[0,n]中，有多少个数可以被3或5整除，再减去在[0,n]中，有多少个数可以被15整除（因为15同时是3和5的倍数，会被重复计算）。具体代码如下：

#include <stdio.h>

int main()
{
    long long n;
    scanf("%lld", &n);

    long long cnt3 = n / 3;  // 可以被3整除的数的个数
    long long cnt5 = n / 5;  // 可以被5整除的数的个数
    long long cnt15 = n / 15;  // 可以被15整除的数的个数

    long long ans = cnt3 + cnt5 - cnt15;  // 最终答案

    if (ans == 0) printf("zero");
    else printf("%lld", ans);

    return 0;
}

注意，由于n的范围较大，需要使用long long类型存储。

Mike_python小

代码问题分析与解决方法

代码中出现时间超限的问题似乎是由于输入上限较大（1e12）导致的。为了优化程序性能，避免不必要的循环和计算，可以采取以下改进措施：

1. 修改循环范围：由于题目要求在[0, n]范围内计算能被3或5整除的数的个数，可以将循环条件修改为i <= n，而不是i <= n。这样可以避免多余的计算。

2. 计算方法优化：使用循环逐个判断每个数是否能被3或5整除并计数的方法较为低效。可以尝试使用数学方法来直接计算满足条件的数的个数。假设n大于等于3，我们可以分别计算出能被3整除的数的个数以及能够被5整除的数的个数，然后再减去同时能被3和5整除的数的个数，即可得到最终结果。

下面是经过改进后的代码：

2. #include <stdio.h>
4. int main()
5. {
6.     long long n;
7.     scanf("%lld", &n);
9.     long long count3 = n / 3; // 能被3整除的数的个数
10.     long long count5 = n / 5; // 能被5整除的数的个数
11.     long long count15 = n / 15; // 能被3和5同时整除的数的个数
13.     long long result = count3 + count5 - count15; // 最终结果
15.     if (result == 0)
16.         printf("zero");
17.     else
18.         printf("%lld", result);
20.     return 0;
21. }

复制代码

这样修改后的代码应该能更高效地计算出满足条件的数的个数，并且避免了时间超限的问题。

希望以上解决方法对您有帮助！如果还有其他问题，请随时提问。

球一个最佳答案谢谢啦！这对我非常重要！