C语言 有没有办法在不改变逻辑和语言的情况下优化以下代码?原因:UVa中超过时间限制

dw1jzc5e  于 11个月前  发布在  其他
关注(0)|答案(1)|浏览(89)


Heres the problem UVa 10110

#include <stdio.h>
int main()
{
    unsigned int n,a,d,i,j;
    while (1)
    {
        scanf("%u",&n);
        if (n==0)
        {
            break;
        }

        a=n/2;

        d=0;

        for (i=1; i<=a; i++)
        {
            if (n%i==0)
            {
                d++;
            }
        }
        if (d%2==0)
        {
            printf("yes\n");
        }
        else
        {
            printf("no\n");
        }
    }
    return 0;
}

字符串
不允许使用任何其他语言:(他们使用的语言:ANSI C 5.3.0 - GNU C编译器,带有选项:-lm -lcrypt -O2 -pipe -ansi -DONLINE_JUDGE运行时间不应超过3秒。

zzlelutf

zzlelutf1#

循环到n/2非常慢,因为代码只需要循环到sqrt(n)

a=n/2;
    d=0;
    for (i=1; i<=a; i++) {
        if (n%i==0) {
          d++;
        }
    }

字符串
可替换为下面的,循环次数最多为sqrt(n)

d=0;
    if (n > 1) { 
      d += 1;
    }
    for (i=2; i < n/i; i++) {
        if (n%i==0) {
          d += 2;
        }
    }
    if (i == n/i) {
        if (n%i==0) {
          d += 1;
        }
    }


由于后面的代码只需要d的均匀性,for (i=1; i < a/i; i++) {循环除了使i接近n的平方根之外没有什么作用。考虑测试n是否是完美的平方,并注意n <= 1的边缘情况。(小心double sqrt(double),因为这会导致意外的舍入。)
注意:不要使用...; i*i < n; i++,因为当nUINT_MAX附近的大值时,i*i可能会溢出。
学究式地,使用一个更宽的类型unsigned,它可能比需要的范围小。建议使用unsigned long

相关问题