UVa 10110题C语言代码优化求助：解决超时且不改变逻辑

问题本质分析 #

你当前的代码通过遍历到n/2统计约数个数，再判断奇偶性来确定灯泡状态，但这种做法的时间复杂度为O(n)。当n接近2^32-1时，循环次数会达到2^31级别，完全无法在3秒内完成，这是超时的核心原因。

实际上这个问题可以通过数学规律大幅简化：

• 灯泡被切换的次数等于其序号的约数个数，初始状态为关闭，奇数次切换后灯亮（输出yes），偶数次则灯灭（输出no）。
• 约数是成对出现的（比如6的约数是1&6、2&3），只有完全平方数的平方根是单独的约数，因此完全平方数的约数个数为奇数，非完全平方数的约数个数为偶数。
• 问题等价于：判断n是否是完全平方数，是则输出yes，否则输出no。

优化后的ANSI C代码 #

#include <stdio.h>
#include <math.h>

int main() {
    unsigned int n;
    while (scanf("%u", &n) == 1 && n != 0) {
        unsigned long long s = (unsigned long long)sqrtl(n);
        // 验证平方值，避免sqrt精度丢失问题
        if (s * s == n) {
            printf("yes\n");
        } else {
            printf("no\n");
        }
    }
    return 0;
}

代码关键点说明 #

1. 时间复杂度优化：直接利用完全平方数的性质，将时间复杂度降到O(1)（sqrt操作属于常数时间）。
2. 精度与溢出处理：
   • 使用sqrtl获取高精度平方根，避免普通sqrt函数的精度丢失问题。
   • 将平方根转换为unsigned long long类型，计算s*s时不会溢出（2^32-1的平方根为65535，其平方远小于unsigned long long的最大值）。
3. 输入逻辑简化：将scanf的返回值作为循环条件，更简洁地处理输入结束的情况。

编译兼容性 #

你提供的编译选项-lm -lcrypt -O2 -pipe -ansi -DONLINE_JUDGE完全兼容这段代码，其中-lm会链接数学库以支持sqrtl函数。

内容的提问来源于stack exchange，提问作者Rahul Das