N变量程序超时问题求助：输入N=9999999时触发Time limit exceeded

原代码的核心问题是双重循环的时间复杂度为O(n²)，当n=9999999时，循环执行次数接近1e14次，远远超出了时间限制的运算能力。

优化思路：用数学公式直接计算结果 #

我们可以通过分析规律避免循环：

• 当i+j为奇数时，必然是一个奇数和一个偶数相加（奇+偶=奇，偶+奇=奇）。
• 分两种情况统计符合条件的对数：
  • 若n为偶数：1~n中奇数、偶数各有n/2个，符合条件的对数为 (n/2)*(n/2) + (n/2)*(n/2) = n²/2
  • 若n为奇数：1~n中奇数有(n+1)/2个，偶数有(n-1)/2个，符合条件的对数为 2 * ((n+1)/2)*((n-1)/2) = (n²-1)/2
• 两种情况可以统一用整数除法 n*n // 2 计算：偶数时n²是偶数，整除2等于n²/2；奇数时n²是奇数，整除2等于(n²-1)/2，完全匹配结果。

优化后的代码 #

for _ in range(int(input())):
    n = int(input())
    print(n * n // 2)

内容的提问来源于stack exchange，提问作者Aayush Puri